华为外包java面试题-Java实现单链表的逆序

来源:千锋教育

发布人:wjy

2023-07-25

推荐

java面试题

　　假设你正在应聘华为外包公司的Java开发岗位，以下是一个可能的面试题案例：

　　面试题目：Java实现单链表的逆序

　　问题描述：

　　请编写一个Java程序，实现对单链表的逆序操作。给定一个单链表的头节点，要求将链表的所有节点反转，并返回反转后的头节点。

　　示例：

　　假设链表为：1 -> 2 -> 3 -> 4 -> 5

　　反转后应该为：5 -> 4 -> 3 -> 2 -> 1

　　解题思路：

　　实现单链表的逆序操作可以使用迭代或递归的方法。下面将为大家提供使用迭代的解题思路。

　　解题步骤：

　　1. 定义三个指针：prev(记录前一个节点)、current(记录当前节点)、next(记录当前节点的下一个节点)。

　　2. 初始时，prev指向null，current指向头节点。

　　3. 在循环中，将current的next指针指向prev，然后将prev指向current，current指向next。

　　4. 重复上述步骤，直到current指向null(到达链表的末尾)。

　　Java代码实现：

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

public class ReverseLinkedList {

    public ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode current = head;
        ListNode next = null;

        while (current != null) {
            next = current.next; // 先保存当前节点的下一个节点
            current.next = prev; // 当前节点的next指针指向前一个节点
            prev = current; // prev指向当前节点，相当于前移一步
            current = next; // current指向下一个节点，相当于前移一步
        }

        return prev; // prev指向原链表的最后一个节点，即反转后的头节点
    }

    // 测试
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        ReverseLinkedList solution = new ReverseLinkedList();
        ListNode reversedHead = solution.reverse(head);

        // 打印反转后的链表
        while (reversedHead != null) {
            System.out.print(reversedHead.val + " -> ");
            reversedHead = reversedHead.next;
        }
        System.out.print("null");
    }
}