內卷大廠系列《連結串列反轉三連擊》

語言: CN / TW / HK

theme: vuepress

一起養成寫作習慣!這是我參與「掘金日新計劃 · 4 月更文挑戰」的第16天,點選檢視活動詳情

一、反轉單向連結串列

給你單鏈表的頭節點 head ,請你反轉連結串列,並返回反轉後的連結串列。

示例 1

java 輸入:head = [1,2,3,4,5] 輸出:[5,4,3,2,1]

示例 2

java 輸入:head = [1,2] 輸出:[2,1]

示例 3

java 輸入:head = [] 輸出:[]

leetcode

1、分析

給定一個單鏈表的頭head,完成連結串列的逆序調整。

方法一:有限變數搞定,定義兩個變數,pre指標,next指標,pre指標指向當前節點的上一個節點,next指標指向當前節點的下一個節點。最優解,時間複雜度O(N),額外空間複雜度O(1)

方法二:遞迴

2、實現

1、方法一

```java public static class ListNode { int val; ListNode next; }

public static ListNode reverseList(ListNode head) { ListNode pre = null; ListNode next = null; while (head != null) { next = head.next; head.next = pre; pre = head; head = next; } return pre; } ```

2、方法二

```java public static class ListNode { int val; ListNode next; }

public static ListNode reverseList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode newList = reverseList(head.next); head.next.next = head; head.next = null; return newList; } ```

二、反轉雙向連結串列

給定一個雙鏈表的頭head,完成連結串列的逆序調整

1、分析

提前記錄下一個節點next,當前節點的next指向pre,當前節點的last指向next,pre的next指向當前節點,當前節點跳下一個

2、實現

```java // 雙鏈表定義 public static class DoubleNode { public int value; public DoubleNode last; public DoubleNode next;

public DoubleNode(int data) {
    value = data;
}

}

// 雙鏈表反轉(兩個指標搞定) public static DoubleNode reverseDoubleList(DoubleNode head) { DoubleNode pre = null; DoubleNode next = null; while (head != null) { next = head.next; head.next = pre; head.last = next; pre = head; head = next; } return pre; } ```

三、反轉部分單向連結串列

給你單鏈表的頭指標 head 和兩個整數 left 和 right ,其中 left <= right 。請你反轉從位置 left 到位置 right 的連結串列節點,返回 反轉後的連結串列 。

示例 1

java 輸入:head = [1,2,3,4,5], left = 2, right = 4 輸出:[1,4,3,2,5]

示例 2

java 輸入:head = [5], left = 1, right = 1 輸出:[5]

進階: 你可以使用一趟掃描完成反轉嗎?

leetcode

1、分析

可能存在換頭的情況,所以函式應該返回調整後的新節點。

方法一:遍歷一遍連結串列,先找到left和right節點,即反轉連結串列的開始部分和結束部分。

  1. 先判斷是否滿足 1≤left≤right≤N,如果不滿足,則直接返回原來的頭節點。
  2. 找到第left-1個節點fPre和第right+1個節點tPos,fPre就是要反轉部分的前一個節點,tPos是反轉部分的後一個節點。把反轉部分先反轉,然後正確的連線fPre和tPos
  3. 如果fPre為null,說明反轉部分是包含頭節點的,則返回新的頭節點,如果fPre不為null,則返回舊的頭節點。

方法二:利用頭插法進行反轉連結串列,待反轉的節點每次都往頭部插入。

2、實現

1、方法一

```java public static class ListNode { int val; ListNode next;

ListNode(int val) {
    this.val = val;
}

}

// 找到反轉連結串列的開始節點和結束節點,正常反轉 public ListNode reverseBetween(ListNode head, int from, int to) { int len = 0; ListNode node1 = head; ListNode fPre = null; // from節點的前一個節點 ListNode tPos = null; // to節點的下一個節點 while (node1 != null) { // 找到反轉連結串列開始節點的前一個節點和結束節點的下一個節點 len++; fPre = len == from - 1 ? node1 : fPre; tPos = len == to + 1 ? node1 : tPos; node1 = node1.next; } if (from > to || from < 1 || to > len) { return head; } node1 = fPre == null ? head : fPre.next; ListNode node2 = node1.next; node1.next = tPos; ListNode next = null; while (node2 != tPos) { // 反轉from到to上的節點 next = node2.next; node2.next = node1; node1 = node2; node2 = next; } if (fPre != null) { fPre.next = node1; return head; } return node1; } ```

2、方法二

```java public static class ListNode { int val; ListNode next;

ListNode(int val) {
    this.val = val;
}

}

public static ListNode reverseBetween(ListNode head, int left, int right) { if (head == null || left == right) { return head; } ListNode newHead = new ListNode(0); newHead.next = head; ListNode pre = newHead; for (int i = 0; i < left - 1; i++) { pre = pre.next; } ListNode cur = pre.next; ListNode next = null; for (int i = 0; i < right - left; i++) { next = cur.next; cur.next = next.next; next.next = pre.next; pre.next = next; } return newHead.next; } ```

四、總結

連結串列相關的問題幾乎都是coding問題,手穩不穩!指標指向問題!

單鏈表:值,一條next指標

雙鏈表:值,一條pre指標,一條next指標

玩出無盡的花樣!