面試：反轉連結清單，位元組跳動Java研發算法題

輸入一個連結清單，反轉連結清單後，輸出新連結清單的表頭。

說明：本題目包含複雜資料結構ListNode

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode currentNode = head;
        ListNode nextNode = head.next;
        ListNode tempNode = null;
        while(nextNode != null){
            tempNode = nextNode.next;
            nextNode.next = currentNode;
            currentNode = nextNode;
            nextNode = tempNode;
        }
        head.next = null;
        return currentNode;
    }
}
           

分析

1. currentNode和nextNode存儲目前節點, tempNode存儲nextNode.next以免斷鍊
2. nextNode不為空為循環條件
3. 循環過程中把nextNode.next指向前一個節點current
4. 最後循環結束current節點為headNode
5. 需要注意最後把原頭結點的next指向null