劍指 Offer 24. 反轉連結清單
定義一個函數，輸入一個連結清單的頭節點，反轉該連結清單并輸出反轉後連結清單的頭節點。
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
限制：
0 <= 節點個數 <= 5000
思考：面試經常手寫的一道題，可以用雙指針交換兩個結點的指向；可以用遞歸不斷轉換兩個結點的指向（重複子問題）
題解：
public ListNode reverseList(ListNode head) {
// 雙指針法
ListNode cur = head, pre = null;
while(cur != null) {
ListNode tmp = cur.next; // 暫存後繼節點 cur.next
cur.next = pre; // 修改 next 引用指向
pre = cur; // pre 暫存 cur
cur = tmp; // cur 通路下一節點
}
return pre;
}
public ListNode reverseList(ListNode head) {
// 遞歸法
if(head == null || head.next == null){ // 遞歸終止條件
return head;
}
ListNode newHead = reverseList(head.next); // 執行遞歸
head.next.next = head; // 将目前節點的下一個 指向自己
head.next = null; // 将自己的後繼去掉
return newHead;
} 19. 删除連結清單的倒數第 N 個結點
給你一個連結清單，删除連結清單的倒數第 n 個結點，并且傳回連結清單的頭結點。
【03/16】力扣押題推薦(反轉連結清單、删除連結清單的倒數第N節點、K個一組翻轉連結清單) 示例 1：
輸入：head = [1,2,3,4,5], n = 2
輸出：[1,2,3,5]
示例 2：
輸入：head = [1], n = 1
輸出：[]
示例 3：
輸入：head = [1,2], n = 1
輸出：[1]
提示：
連結清單中結點的數目為 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
思考：我們可以周遊一遍連結清單，找到對應位置删除；快指針先走n步，當快指針為null時，删除慢指針的位置
題解：
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head); // 保留的頭節點
int length = getLength(head); // 擷取連結清單長度
ListNode cur = dummy;
for (int i = 1; i < length - n + 1; ++i) { // 周遊到 L-n+1的位置
cur = cur.next;
}
cur.next = cur.next.next; // 删除節點
ListNode ans = dummy.next; // 傳回保留的頭節點
return ans;
}
public int getLength(ListNode head) { /*周遊一遍，計算連結清單長度*/
int length = 0;
while (head != null) {
++length;
head = head.next;
}
return length;
} // 快指針先走n步，當快指針為null時，删除慢指針的位置
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head); // 保留的頭節點
ListNode first = head; // 快指針
ListNode second = dummy; // 慢指針
for (int i = 0; i < n; ++i) // 快指針先走的n的位置
first = first.next;
while (first != null) { // 同時向後移動
first = first.next;
second = second.next;
}
second.next = second.next.next; // 删除節點
ListNode ans = dummy.next; // 傳回保留的頭節點
return ans;
} 25. K 個一組翻轉連結清單
給你一個連結清單，每 k 個節點一組進行翻轉，請你傳回翻轉後的連結清單。
k 是一個正整數，它的值小于或等于連結清單的長度。
如果節點總數不是 k 的整數倍，那麼請将最後剩餘的節點保持原有順序。
進階：
你可以設計一個隻使用常數額外空間的算法來解決此問題嗎？
你不能隻是單純的改變節點内部的值，而是需要實際進行節點交換。
示例 1：
【03/16】力扣押題推薦(反轉連結清單、删除連結清單的倒數第N節點、K個一組翻轉連結清單) 輸入：head = [1,2,3,4,5], k = 2
輸出：[2,1,4,3,5]
示例 2：
輸入：head = [1,2,3,4,5], k = 3
輸出：[3,2,1,4,5]
示例 3：
輸入：head = [1,2,3,4,5], k = 1
輸出：[1,2,3,4,5]
示例 4：
輸入：head = [1], k = 1
輸出：[1]
提示：
清單中節點的數量在範圍 sz 内
1 <= sz <= 5000
0 <= Node.val <= 1000
1 <= k <= sz
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || head.next == null) { // 遞歸終止條件
return head;
}
// 找到
ListNode tail = head;
for (int i = 0; i < k; i++) {
//剩餘數量小于k的話，則不需要反轉。
if (tail == null) {
return head;
}
tail = tail.next;
}
// 反轉前 k 個元素
ListNode newHead = reverse(head, tail);
// 下一輪的開始的地方就是tail
head.next = reverseKGroup(tail, k);
return newHead;
}
/*
左閉又開區間
*/
/**
* @param head 整個未反轉的連結清單
* @param tail 本輪不需要反轉的連結清單
* @return
*/
private ListNode reverse(ListNode head, ListNode tail) {
ListNode pre = null;
ListNode next = null;
// 對其進行翻轉。并傳回翻轉後的頭結點
while (head != tail) {
// 每次都将目前節點的指針反轉
// 報錯為反轉的節點
next = head.next;
// 待反轉的節點指向pre（pre會向後移動的）
head.next = pre;
// pre重新指向目前頭結點
pre = head;
// head向後移動到未反轉的節點
head = next;
}
return pre;
} /**
* 時間複雜度O(n)，空間複雜度O(1) 雙指針周遊 ，假設；head=[1,2,3,4,5] ,k=2
*
* @param head 連結清單執行個體頭結點
* @param k 翻轉的K數
* @return
*/
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || head.next == null) {
return head;
}
// 建立一個空節點[0]
ListNode dummy = new ListNode(0);
// 将新建立的空結點 指向head節點[0 -> 1,2,3,4,5],此時dummy=[0,1,2,3,4,5]
dummy.next = head;
// 設定兩個記錄指針，此時pre=[0,1,2,3,4,5],此時end=[0,1,2,3,4,5]
ListNode pre = dummy;
ListNode end = dummy;
// 周遊連結清單
while (end.next != null) {
// 這裡設計的很巧妙，周遊k次的end，使end最終等于需要交換的節點,此時end=[2,3,4,5]
for (int i = 0; i < k && end != null; i++) {
end = end.next;
}
// end如果為null，就跳對外連結表的周遊，證明已經把所有需要的節點交換完畢
if (end == null) {
break;
}
// 這是建立兩個交換指針 ，start=[1,2,3,4,5] next=[3,4,5]
// 記錄要翻轉連結清單的頭節點
ListNode start = pre.next;
// 記錄下end.next,友善後面連結連結清單
ListNode next = end.next;
// 将end下一個指向null，目的是斷開連結清單，end=[2,null ...]同時start=[1,2,null ...] ,就是end=[2],start=[1,2],
end.next = null;
// 拿到start需要反轉的連結清單開始反轉，此時執行完反轉方法 pre=[0,2,1],dummy=[0,2,1],head=[1],start=[1],end=[2,1] , next=[3,4,5]
pre.next = reverse(start);
// 翻轉後頭節點變到最後。通過.next把斷開的連結清單重新連結。start=[1,3,4,5],此時pre=[0,2,1,3,4,5],dummy=[0,2,1,3,4,5],end=[2,1,3,4,5] , next=[3,4,5]
start.next = next;
// 将pre換成下次要翻轉的連結清單的頭結點的上一個節點。即start pre=[1,3,4,5]
pre = start;
// 翻轉結束，将end置為下次要翻轉的連結清單的頭結點的上一個節點。即start end=[1,3,4,5] , 其餘同理（周遊第二遍dummy=[0,2,1,4,3,5],pre=[3,5]end=[3,5]）
end = pre;
}
// 傳回連結清單頭結點
return dummy.next;
}
/**
* 反轉連結清單，此時的head是需要反轉的連結清單
*/
private ListNode reverse(ListNode head) {
//單連結清單為空或隻有一個節點，直接傳回原單連結清單
if (head == null || head.next == null) {
return head;
}
// 創造目前節點的前一個節點
ListNode pre = null;
// 目前節點指針,此時curr就是[1,2]
ListNode curr = head;
// 周遊目前節點的連結清單
while (curr != null) {
// 記錄指向下一個節點,儲存目前節點後面的連結清單，next=[2] ; 第二次循環next=null
ListNode next = curr.next;
// 将curr目前節點next域指向前一個節點pre，此時curr=[1],pre=null,head=[1] ; 第二次循環next=null，curr=[2，1]
curr.next = pre;
// pre指針向後移動，此時pre隻想目前節點 pre=[1] ; 第二次循環pre=[2,1]
pre = curr;
// cur指針向後移動。下一個節點變成目前節點 curr=[2],pre=[1],head=[1] ; 第二次循環curr = null,pre=[2,1],head=[1]
curr = next;
}
// 傳回已交換連結清單的頭結點
return pre;
}