基础数据结构—你需要重排链表

重排链表

思路

本篇将给出三种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 服务器租用

本文地址：http://bhae.cn/html/077a28399639.html