leetcode-143

LeetCode 143. 重排链表

1 题目描述

• 题目链接：143. 重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

$L_0 → L_1 → … → L_{n - 1} → L_n$

请将其重新排列后变为：

$L_0 → L_n → L_1 → L_{n - 1} → L_2 → L_{n - 2} → …$

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例1：

输入: head = [1,2,3,4]
输出: [1,4,2,3]

示例2：

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

2 思路

• 辅助数组

  • 创建一个数组存放每个节点，然后设置两个指针，分别指向数组开头和末尾，将开头节点的 next 域指向末尾节点，末尾节点的 next 域指向开头节点的下个节点，即：

    int i = 0, j = index - 1;       //i为开头指针，j为末尾指针
    while(i<j){
        tmp[i++]->next = tmp[j];    //开头节点next指向末尾节点并将指针后移
        if(i>=j){                   //判断是否两个指针相遇
            break;                  //相遇说明重排完毕
        }     
        tmp[j--]->next = tmp[i];    //将末尾节点next指向开头结(开头指针已经后移一位)
    }

  • 完整代码如下:

    /**
    * Definition for singly-linked list.
    * struct ListNode {
    *     int val;
    *     struct ListNode *next;
    * };
    */
    
    void reorderList(struct ListNode* head){
        if(head == NULL) return;
    
        struct ListNode *tmp[50001];    
        struct ListNode *cur = head;
        int index = 0;
        while(cur!=NULL){           //将每个节点存入数组
            tmp[index++] = cur;
            cur = cur->next;
        }
        int i = 0, j = index - 1;
        while(i<j){
            tmp[i++]->next = tmp[j];
            if(i>=j){
                break;
            }     
            tmp[j--]->next = tmp[i];
        }
        tmp[i]->next = NULL;
    }

  • 代码性能

    • 时间复杂度： O(n)
    • 空间复杂度： O(n)

• 原地重排
    此题实际上是将链表的右半部分进行反转，然后将左右两部分进行合并。因而可以分三步：1. 找中间节点；2. 反转右半部分；3. 合并链表.

  • 找中间节点(876. 链表的中间结点)
    • 设置快慢双指针，快指针每次走两步，慢指针每次走一步，当快指针走到末端则慢指针刚好走到中间节点.

      ListNode* middleNode(ListNode* head) {
          ListNode *fast = head, *slow = head;
          while(fast && fast->next){
              fast =fast->next->next;
              slow = slow->next;
          }
          return slow;
      }

  • 反转链表
    • 迭代实现：设置前置节点prev，初始化为 nullptr, 然后遍历整个链表，先存储当前遍历到的链表节点的 next 域，然后将当前节点的 next 指向 prev ，直至遍历完成，将 prev 返回即可。

      ListNode* reverseList(ListNode* head) {
          ListNode *pre = nullptr, *cur = head;
          while(cur){
              ListNode *next = cur->next;
              cur->next = pre;
              pre = cur;
              cur = next;
          }
          return pre;
      }

    • 递归实现

      struct ListNode* reverseList(struct ListNode* head){
          if(head == NULL||head->next == NULL){
              return head;
          }
          struct ListNode* newHead;
          newHead = reverseList(head->next);  //newHead是最后一层的return
          head->next->next = head;            //然后倒数第二次return那个newhead
          head->next = NULL;
          return newHead;         //所以这里return的其实就是最后一层的head
      }

  • 合并链表
    • 将左半部分当前节点的 next 指向右半部分当前节点，将右半部分当前节点的 next 指向左半部分当前节点的下个节点，并将左右两部分的指针后移。这里由于需要用到两个指针的 next 节点，所以改变指向时需要先将各自的 next 节点存下来。

      ListNode* mergeList(ListNode* root1, ListNode* root2){
          ListNode* left = root1, *right = root2;
          while(left && right){
              ListNode *left_next = left->next;
              ListNode *right_next = right->next;
              left->next = right;
              right->next = left_next;
              left = left_next;
              right = right_next;
          }
          return root1;
      }

  • 将以上三部分合起来即可完成本题，完整代码如下：

    /**
    * Definition for singly-linked list.
    * struct ListNode {
    *     int val;
    *     ListNode *next;
    *     ListNode() : val(0), next(nullptr) {}
    *     ListNode(int x) : val(x), next(nullptr) {}
    *     ListNode(int x, ListNode *next) : val(x), next(next) {}
    * };
    */
    class Solution {
    public:
        ListNode* reverse(ListNode* head){
            ListNode *prev = nullptr, *cur = head;
            while(cur){
                ListNode *next = cur->next;
                cur->next = prev;
                prev = cur;
                cur = next;
            }
            return prev;
        }
    
        ListNode* findMidNode(ListNode* head){
            ListNode *slow = head, *fast = head;
            while(fast && fast->next && fast->next->next){      //找中间节点
                slow = slow->next;
                fast = fast->next->next;
            }
            return slow;
        }
    
        void mergeList(ListNode* root1, ListNode* root2){
            ListNode* left = root1, *right = root2;
            while(left && right){
                ListNode *left_next = left->next;
                ListNode *right_next = right->next;
                left->next = right;
                right->next = left_next;
                left = left_next;
                right = right_next;
            }
        }
    
        void reorderList(ListNode* head) {
            ListNode *mid = findMidNode(head);
            mid = reverse(mid);     //反转后半部分链表
            mergeList(head, mid);
        }
    };