【Java】單連結清單反轉詳解

題目描述

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

代碼

/*
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 preNode = null;
        //下一個節點指針
        ListNode nextNode = null;
 
        while (head != null){
            nextNode = head.next;    //nextNode 指向下一個節點
            head.next = preNode;
            preNode = head;          //preNode 指針向後移動
            head = nextNode;         
        }
        return preNode;
    }
}
           

分析

1->2->3->4

第一步

nextNode指向2，意味着nextNode就是2->3->4

第二步

head.next為null，意味着1和2斷開，此時head就是1

第三步

preNode為1，這是反轉後的連結清單

第四步

head重新指派為nextNode，也就是2->3->4

繼續while循環

nextNode變為3->4

2和3斷開，2的下一個指向preNode也就是1，preNode變為2->1

head重新指派nextNode也就是3->4