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

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

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

　　問(wèn)題描述：

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

　　示例：

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

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

　　解題思路：

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

　　解題步驟：

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

　　2. 初始時(shí)，prev指向null，current指向頭節(jié)點(diǎn)。

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

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

　　Java代碼實(shí)現(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é)點(diǎn)的下一個(gè)節(jié)點(diǎn)
            current.next = prev; // 當(dāng)前節(jié)點(diǎn)的next指針指向前一個(gè)節(jié)點(diǎn)
            prev = current; // prev指向當(dāng)前節(jié)點(diǎn)，相當(dāng)于前移一步
            current = next; // current指向下一個(gè)節(jié)點(diǎn)，相當(dāng)于前移一步
        }

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

    // 測(cè)試
    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");
    }
}

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