【每日一題】反轉連結清單

前言

工作之後每天都是CRUD，CRUD多了腦袋也跟着生鏽，為了拯救一下自個貧瘠的腦瓜子，也為了以後的大廠夢，決定每日從牛客網上找個題目來練練手，剛開始先挑個簡單的來提升一下自信心。

正文

反轉連結清單是牛客網中上周最熱且比較簡單題目，就它了，開搞。

題目描述

反轉連結清單：傳入一個連結清單的表頭，反轉連結清單後傳回新連結清單的表頭。

連結清單節點結構如下：

class ListNode{
        Object value;
        ListNode next;
        public ListNode(Object value){
            this.value = value;
        }
    }
           

輸入樣例

{1,2,3}

輸出樣例

{3,2,1}

分析

題目很簡單，用我們大腦思考就是周遊每一個節點将目前節點的next指向它的上一個節點即可。

用代碼處理的話我們需要注意的是防止把目前節點的next指向它前一個後會丢失對它原next引用的問題。

此時我們就需要引入一些輔助變量幫我們記錄前一個節點、目前節點、下一個節點。僞代碼如下：

// head是出入的連結清單頭
		// 初始用頭節點做上一個節點
        ListNode preNode = head;
        // 頭節點的下一個節點為目前節點
        ListNode currentNode = preNode.next;
        // 目前節點的下一個節點做下一個節點
        ListNode nextNode = currentNode.next;
        // 初始時候直接将目前節點的下一個指向它的前一個節點，接下來周遊連結清單從next節點開始
        currentNode.next = preNode;
        // 一定要把頭節點的下一個指針指向null，因為原本head.next指向currentNode，上一步又相當于把currentNode.next = head。如果不把head.next置為null會出現head和currentNode的循環指向了。
        head.next = null;
           

接下來我們分析周遊時我們需要做什麼事情：

1、将currenNode和nextNode的連結關系反轉

2、将nextNode指派給currentNode，将nextNode.next指派給nextNode

代碼實作如下：

while (nextNode!=null){
			// 輔助變量，防止nextNode.next的引用丢失
            ListNode newNext = nextNode.next;
            // 反轉currentNode和nextNode的連結關系
            nextNode.next = currentNode;
            // 重置currentNode
            currentNode = nextNode;
            // 重置nextNode
            nextNode = newNext;
        }
           

至此核心代碼已經完成，但是還需要注意一點就是如果head的長度為0和1時需要做以下特殊處理，不然容易出現空指針異常。

完整代碼如下：

public static ListNode reverseList(ListNode head){
        // 當傳入的連結清單為空就傳回null
        if(head==null){
            return null;
        }
        ListNode preNode = head;
        ListNode currentNode = preNode.next;
        // 如果連結清單隻有一個元素，怎麼反轉都還是這個元素，直接傳回即可
        if(currentNode==null){
            return head;
        }
        ListNode nextNode = currentNode.next;
        // 初始時候直接将目前節點的下一個指向它的前一個節點，接下來周遊連結清單從next節點開始
        currentNode.next = preNode;
        // 一定要把頭節點的下一個指針指向null，因為原本head.next指向currentNode，上一步又相當于把currentNode.next = head。如果不把head.next置為null會出現head和currentNode的循環指向了。
        head.next = null;
        while (nextNode!=null){
            // 輔助變量，防止nextNode.next的引用丢失
            ListNode newNext = nextNode.next;
            // 反轉currentNode和nextNode的連結關系
            nextNode.next = currentNode;
            // 重置currentNode
            currentNode = nextNode;
            // 重置nextNode
            nextNode = newNext;
        }
        return currentNode;
    }