溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要為大家展示了“LeetCode反轉鏈表的方式有哪些”，內容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領大家一起研究并學習一下“LeetCode反轉鏈表的方式有哪些”這篇文章吧。
問題描述
定義一個函數，輸入一個鏈表的頭節點，反轉該鏈表并輸出反轉后鏈表的頭節點。
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
限制：
0 <= 節點個數 <= 5000
使用棧解決
鏈表的反轉是老生常談的一個問題了，同時也是面試中常考的一道題。最簡單的一種方式就是使用棧，因為棧是先進后出的。實現原理就是把鏈表節點一個個入棧，當全部入棧完之后再一個個出棧，出棧的時候在把出棧的結點串成一個新的鏈表。原理如下
代碼比較簡單，來看下
1public ListNode reverseList(ListNode head) {
2 Stack<ListNode> stack = new Stack<>();
3 //把鏈表節點全部摘掉放到棧中
4 while (head != null) {
5 stack.push(head);
6 head = head.next;
7 }
8 if (stack.isEmpty())
9 return null;
10 ListNode node = stack.pop();
11 ListNode dummy = node;
12 //棧中的結點全部出棧，然后重新連成一個新的鏈表
13 while (!stack.isEmpty()) {
14 ListNode tempNode = stack.pop();
15 node.next = tempNode;
16 node = node.next;
17 }
18 //最后一個結點就是反轉前的頭結點，一定要讓他的next
19 //等于空，否則會構成環
20 node.next = null;
21 return dummy;
22}
雙鏈表求解
雙鏈表求解是把原鏈表的結點一個個摘掉，每次摘掉的鏈表都讓他成為新的鏈表的頭結點，然后更新新鏈表。下面以鏈表1→2→3→4為例畫個圖來看下。
他每次訪問的原鏈表節點都會成為新鏈表的頭結點，最后再來看下代碼
1public ListNode reverseList(ListNode head) {
2 //新鏈表
3 ListNode newHead = null;
4 while (head != null) {
5 //先保存訪問的節點的下一個節點，保存起來
6 //留著下一步訪問的
7 ListNode temp = head.next;
8 //每次訪問的原鏈表節點都會成為新鏈表的頭結點，
9 //其實就是把新鏈表掛到訪問的原鏈表節點的
10 //后面就行了
11 head.next = newHead;
12 //更新新鏈表
13 newHead = head;
14 //重新賦值，繼續訪問
15 head = temp;
16 }
17 //返回新鏈表
18 return newHead;
19}
遞歸解決
我們再來回顧一下遞歸的模板，終止條件，遞歸調用，邏輯處理。
1public ListNode reverseList(參數0) {
2 if (終止條件)
3 return;
4
5 邏輯處理（可能有，也可能沒有，具體問題具體分析）
6
7 //遞歸調用
8 ListNode reverse = reverseList(參數1);
9
10 邏輯處理（可能有，也可能沒有，具體問題具體分析）
11}
終止條件就是鏈表為空，或者是鏈表沒有尾結點的時候，直接返回
if (head == null || head.next == null) return head;
遞歸調用是要從當前節點的下一個結點開始遞歸。邏輯處理這塊是要把當前節點掛到遞歸之后的鏈表的末尾，看下代碼
1public ListNode reverseList(ListNode head) {
2 //終止條件
3 if (head == null || head.next == null)
4 return head;
5 //保存當前節點的下一個結點
6 ListNode next = head.next;
7 //從當前節點的下一個結點開始遞歸調用
8 ListNode reverse = reverseList(next);
9 //reverse是反轉之后的鏈表，因為函數reverseList
10 // 表示的是對鏈表的反轉，所以反轉完之后next肯定
11 // 是鏈表reverse的尾結點，然后我們再把當前節點
12 //head掛到next節點的后面就完成了鏈表的反轉。
13 next.next = head;
14 //這里head相當于變成了尾結點，尾結點都是為空的，
15 //否則會構成環
16 head.next = null;
17 return reverse;
18}
因為遞歸調用之后head.next節點就會成為reverse節點的尾結點，我們可以直接讓head.next.next = head;，這樣代碼會更簡潔一些，看下代碼
1public ListNode reverseList(ListNode head) {
2 if (head == null || head.next == null)
3 return head;
4 ListNode reverse = reverseList(head.next);
5 head.next.next = head;
6 head.next = null;
7 return reverse;
8}
這種遞歸往下傳遞的時候基本上沒有邏輯處理，當往回反彈的時候才開始處理，也就是從鏈表的尾端往前開始處理的。我們還可以再來改一下，在鏈表遞歸的時候從前往后處理，處理完之后直接返回遞歸的結果，這就是所謂的尾遞歸，這種運行效率要比上一種好很多
1public ListNode reverseList(ListNode head) {
2 return reverseListInt(head, null);
3}
4
5private ListNode reverseListInt(ListNode head, ListNode newHead) {
6 if (head == null)
7 return newHead;
8 ListNode next = head.next;
9 head.next = newHead;
10 return reverseListInt(next, head);
11}
尾遞歸雖然也會不停的壓棧，但由于最后返回的是遞歸函數的值，所以在返回的時候都會一次性出棧，不會一個個出棧這么慢。但如果我們再來改一下，像下面代碼這樣又會一個個出棧了
1public ListNode reverseList(ListNode head) {
2 return reverseListInt(head, null);
3}
4
5private ListNode reverseListInt(ListNode head, ListNode newHead) {
6 if (head == null)
7 return newHead;
8 ListNode next = head.next;
9 head.next = newHead;
10 ListNode node = reverseListInt(next, head);
11 return node;
12}以上是“LeetCode反轉鏈表的方式有哪些”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
