基礎數據結構—你需要重排鏈表
作者：程序員Carl
鏈表是一種常見的基礎數據結構，結構體指針在這里得到了充分的利用。鏈表可以動態的進行存儲分配，也就是說，鏈表是一個功能極為強大的數組，他可以在節點中定義多種數據類型，還可以根據需要隨意增添.
重排鏈表
思路
本篇將給出三種C++實現的方法
- 數組模擬
- 雙向隊列模擬
- 直接分割鏈表
方法一
把鏈表放進數組中，然后通過雙指針法，一前一后，來遍歷數組，構造鏈表。
代碼如下：
- class Solution {
- public:
- void reorderList(ListNode* head) {
- vector<ListNode*> vec;
- ListNode* cur = head;
- if (cur == nullptr) return;
- while(cur != nullptr) {
- vec.push_back(cur);
- cur = cur->next;
- }
- cur = head;
- int i = 1;
- int j = vec.size() - 1; // i j為之前前后的雙指針
- int count = 0; // 計數，偶數去后面，奇數取前面
- while (i <= j) {
- if (count % 2 == 0) {
- cur->next = vec[j];
- j--;
- } else {
- cur->next = vec[i];
- i++;
- }
- cur = cur->next;
- count++;
- }
- cur->next = nullptr; // 注意結尾
- }
- };
方法二
把鏈表放進雙向隊列，然后通過雙向隊列一前一后彈出數據，來構造新的鏈表。這種方法比操作數組容易一些，不用雙指針模擬一前一后了
- class Solution {
- public:
- void reorderList(ListNode* head) {
- deque<ListNode*> que;
- ListNode* cur = head;
- if (cur == nullptr) return;
- while(cur->next != nullptr) {
- que.push_back(cur->next);
- cur = cur->next;
- }
- cur = head;
- int count = 0; // 計數，偶數去后面，奇數取前面
- ListNode* node;
- while(que.size()) {
- if (count % 2 == 0) {
- node = que.back();
- que.pop_back();
- } else {
- node = que.front();
- que.pop_front();
- }
- count++;
- cur->next = node;
- cur = cur->next;
- }
- cur->next = nullptr; // 注意結尾
- }
- };
方法三
將鏈表分割成兩個鏈表，然后把第二個鏈表反轉，之后在通過兩個鏈表拼接成新的鏈表。
如圖：
這種方法，比較難，平均切割鏈表，看上去很簡單，真正代碼寫的時候有很多細節，同時兩個鏈表最后拼裝整一個新的鏈表也有一些細節需要注意!
代碼如下：
- class Solution {
- private:
- // 反轉鏈表
- ListNode* reverseList(ListNode* head) {
- ListNode* temp; // 保存cur的下一個節點
- ListNode* cur = head;
- ListNode* pre = NULL;
- while(cur) {
- temp = cur->next; // 保存一下 cur的下一個節點，因為接下來要改變cur->next
- cur->next = pre; // 翻轉操作
- // 更新pre 和 cur指針
- pre = cur;
- cur = temp;
- }
- return pre;
- }
- public:
- void reorderList(ListNode* head) {
- if (head == nullptr) return;
- // 使用快慢指針法，將鏈表分成長度均等的兩個鏈表head1和head2
- // 如果總鏈表長度為奇數，則head1相對head2多一個節點
- ListNode* fast = head;
- ListNode* slow = head;
- while (fast && fast->next && fast->next->next) {
- fast = fast->next->next;
- slow = slow->next;
- }
- ListNode* head1 = head;
- ListNode* head2;
- head2 = slow->next;
- slow->next = nullptr;
- // 對head2進行翻轉
- head2 = reverseList(head2);
- // 將head1和head2交替生成新的鏈表head
- ListNode* cur1 = head1;
- ListNode* cur2 = head2;
- ListNode* cur = head;
- cur1 = cur1->next;
- int count = 0; // 偶數取head2的元素，奇數取head1的元素
- while (cur1 && cur2) {
- if (count % 2 == 0) {
- cur->next = cur2;
- cur2 = cur2->next;
- } else {
- cur->next = cur1;
- cur1 = cur1->next;
- }
- count++;
- cur = cur->next;
- }
- if (cur2 != nullptr) { // 處理結尾
- cur->next = cur2;
- }
- if (cur1 != nullptr) {
- cur->next = cur1;
- }
- }
- };
其他語言版本
Java
- // 方法三
- public class ReorderList {
- public void reorderList(ListNode head) {
- ListNode fast = head, slow = head;
- //求出中點
- while (fast.next != null && fast.next.next != null) {
- slow = slow.next;
- fast = fast.next.next;
- }
- //right就是右半部分 12345 就是45 1234 就是34
- ListNode right = slow.next;
- //斷開左部分和右部分
- slow.next = null;
- //反轉右部分 right就是反轉后右部分的起點
- right = reverseList(right);
- //左部分的起點
- ListNode left = head;
- //進行左右部分來回連接
- //這里左部分的節點個數一定大于等于右部分的節點個數 因此只判斷right即可
- while (right != null) {
- ListNode curLeft = left.next;
- left.next = right;
- left = curLeft;
- ListNode curRight = right.next;
- right.next = left;
- right = curRight;
- }
- }
- public ListNode reverseList(ListNode head) {
- ListNode headNode = new ListNode(0);
- ListNode cur = head;
- ListNode next = null;
- while (cur != null) {
- next = cur.next;
- cur.next = headNode.next;
- headNode.next = cur;
- cur = next;
- }
- return headNode.next;
- }
- }
- // 方法一 Java實現，使用數組存儲節點
- class Solution {
- public void reorderList(ListNode head) {
- // 雙指針的做法
- ListNode cur = head;
- // ArrayList底層是數組，可以使用下標隨機訪問
- List<ListNode> list = new ArrayList<>();
- while (cur != null){
- list.add(cur);
- cur = cur.next;
- }
- cur = head; // 重新回到頭部
- int l = 1, r = list.size() - 1; // 注意左邊是從1開始
- int count = 0;
- while (l <= r){
- if (count % 2 == 0){
- // 偶數
- cur.next = list.get(r);
- r--;
- }else {
- // 奇數
- cur.next = list.get(l);
- l++;
- }
- // 每一次指針都需要移動
- cur = cur.next;
- count++;
- }
- // 注意結尾要結束一波
- cur.next = null;
- }
- }
- // 方法二：使用雙端隊列，簡化了數組的操作，代碼相對于前者更簡潔（避免一些邊界條件）
- class Solution {
- public void reorderList(ListNode head) {
- // 使用雙端隊列的方法來解決
- Deque<ListNode> de = new LinkedList<>();
- // 這里是取head的下一個節點，head不需要再入隊了，避免造成重復
- ListNode cur = head.next;
- while (cur != null){
- de.offer(cur);
- cur = cur.next;
- }
- cur = head; // 回到頭部
- int count = 0;
- while (!de.isEmpty()){
- if (count % 2 == 0){
- // 偶數，取出隊列右邊尾部的值
- cur.next = de.pollLast();
- }else {
- // 奇數，取出隊列左邊頭部的值
- cur.next = de.poll();
- }
- cur = cur.next;
- count++;
- }
- cur.next = null;
- }
- }
Python
- # 方法二 雙向隊列
- class Solution:
- def reorderList(self, head: ListNode) -> None:
- """
- Do not return anything, modify head in-place instead.
- """
- d = collections.deque()
- tmp = head
- while tmp.next: # 鏈表除了首元素全部加入雙向隊列
- d.append(tmp.next)
- tmp = tmp.next
- tmp = head
- while len(d): # 一后一前加入鏈表
- tmp.next = d.pop()
- tmp = tmp.next
- if len(d):
- tmp.next = d.popleft()
- tmp = tmp.next
- tmp.next = None # 尾部置空
- # 方法三 反轉鏈表
- class Solution:
- def reorderList(self, head: ListNode) -> None:
- if head == None or head.next == None:
- return True
- slow, fast = head, head
- while fast and fast.next:
- slow = slow.next
- fast = fast.next.next
- right = slow.next # 分割右半邊
- slow.next = None # 切斷
- right = self.reverseList(right) #反轉右半邊
- left = head
- # 左半邊一定比右半邊長, 因此判斷右半邊即可
- while right:
- curLeft = left.next
- left.next = right
- left = curLeft
- curRight = right.next
- right.next = left
- right = curRight
- def reverseList(self, head: ListNode) -> ListNode:
- cur = head
- pre = None
- while(cur!=None):
- temp = cur.next # 保存一下cur的下一個節點
- cur.next = pre # 反轉
- pre = cur
- cur = temp
- return pre
責任編輯：姜華
來源：
代碼隨想錄
