華為外包java面試題-Java實現(xiàn)單鏈表的逆序

　　假設(shè)你正在應(yīng)聘華為外包公司的Java開發(fā)崗位，以下是一個可能的面試題案例：

　　面試題目：Java實現(xiàn)單鏈表的逆序

　　問題描述：

　　請編寫一個Java程序，實現(xiàn)對單鏈表的逆序操作。給定一個單鏈表的頭節(jié)點，要求將鏈表的所有節(jié)點反轉(zhuǎn)，并返回反轉(zhuǎn)后的頭節(jié)點。

　　示例：

　　假設(shè)鏈表為：1 -> 2 -> 3 -> 4 -> 5

　　反轉(zhuǎn)后應(yīng)該為：5 -> 4 -> 3 -> 2 -> 1

　　解題思路：

　　實現(xiàn)單鏈表的逆序操作可以使用迭代或遞歸的方法。下面將為大家提供使用迭代的解題思路。

　　解題步驟：

　　1. 定義三個指針：prev(記錄前一個節(jié)點)、current(記錄當(dāng)前節(jié)點)、next(記錄當(dāng)前節(jié)點的下一個節(jié)點)。

　　2. 初始時，prev指向null，current指向頭節(jié)點。

　　3. 在循環(huán)中，將current的next指針指向prev，然后將prev指向current，current指向next。

　　4. 重復(fù)上述步驟，直到current指向null(到達鏈表的末尾)。

　　Java代碼實現(xiàn)：

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; // 先保存當(dāng)前節(jié)點的下一個節(jié)點
            current.next = prev; // 當(dāng)前節(jié)點的next指針指向前一個節(jié)點
            prev = current; // prev指向當(dāng)前節(jié)點，相當(dāng)于前移一步
            current = next; // current指向下一個節(jié)點，相當(dāng)于前移一步
        }

        return prev; // prev指向原鏈表的最后一個節(jié)點，即反轉(zhuǎn)后的頭節(jié)點
    }

    // 測試
    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);

        // 打印反轉(zhuǎn)后的鏈表
        while (reversedHead != null) {
            System.out.print(reversedHead.val + " -> ");
            reversedHead = reversedHead.next;
        }
        System.out.print("null");
    }
}

　　這是一個典型的面試題目，面試官可能會根據(jù)你的解答展開更多問題，例如如何使用遞歸實現(xiàn)鏈表逆序，或者如何處理特殊情況(如空鏈表)。在面試過程中，除了正確的解答問題，展示良好的溝通和思考能力也是非常重要的。希望以上面試題案例對你有所幫助!