本文共 2634 字，大约阅读时间需要 8 分钟。

143. 重排链表

难度中等

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，

将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→… 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 示例 1: 给定链表 1->2->3->4, 重新排列为 1->4->2->3. 示例 2: 给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

思路1.0：

（1）使用栈来辅助“第i个节点连上第n-i个节点”

代码1.0（未过）：

class Solution {
   public:    void reorderList(ListNode* head) {
           if (head == NULL) return;        stack
   
     stk;        ListNode* cur = head;        while (cur != NULL) {
               stk.push(cur);            cur = cur->next;        }                cur = head;        while (cur != NULL && cur->next != NULL) {
               ListNode* p = cur->next;            ListNode* right = stk.top();            stk.pop();                        cur->next = right;            right->next = p;            cur = p;        }        if (cur != NULL) cur->next = NULL;        return ;    }};
   

链表指针处理出现问题，自己这个还是暴力法，去题解逛逛

思路2.0（已看题解）：

（1）使用unordered_map来存储链表信息，减少访问时间成本

代码2.0：

class Solution {
     public:      void reorderList(ListNode* head) {
             if (head == NULL) return;          unordered_map
   
     hash;          int idx = 0;          while (head != NULL) {
                 hash[idx] = head;              ++idx;              head = head->next;          }          --idx;          if (idx < 2) return;          int left = 0;          while (left < idx) {
                 hash[left]->next = hash[idx];              ++left;              if (left == idx) break;              hash[idx]->next = hash[left];              --idx;          }                    hash[left]->next = NULL;          return;      }  };
   

多用哈希表存储链表信息

思路3.0（递归，已看题解）：

每次递归的行为

（1）先把从下一层传来的尾节点这一信息进行处理，头节点指向尾节点，尾节点指向下一对的头节点

（2）返回上一层需要的尾节点

代码3.0：

class Solution {
     public:      ListNode* helper(ListNode* head, int len) {
             if (len == 1) {
                 ListNode* outHead = head->next;              head->next = NULL;              return outHead;          }          else if (len == 2) {
                 ListNode* outHead = head->next->next;              head->next->next = NULL;              return outHead;          }          ListNode* tail = helper(head->next, len - 2);          ListNode* nextHead = head->next;          head->next = tail;          ListNode* outHead = tail->next;          tail->next = nextHead;          return outHead;      }      void reorderList(ListNode* head) {
             if (head == NULL || head->next == NULL || head->next->next == NULL) return;          int len = 0;          ListNode* cur = head;          while (cur != NULL) {
                 ++len;              cur = cur->next;          }          helper(head, len);          return;      }  };

转载地址：http://yvowi.baihongyu.com/