143.重排链表

发表于： 分类于：
字数： 774 阅读：≈ 2分钟

⛓︎ 143.重排链表

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

L0 → L1 → … → Ln - 1 → Ln 请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例

示例 1：

img

1
2

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

示例 2：

img

1
2

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

思路

基本思想

根据题目的描述，需要将链表的节点取下来组成一个新的链表，并且取节点的顺序有限制，必须头先取一个插入新链表，之后尾部取一个插入新链表，插入的顺序为尾插法，知道这个流程之后就是使用代码模拟

为了不出现空指针，先给新链表中擦干入一个节点，并且为了可以首尾取节点，也就是随机访问，需要先遍历一遍链表，将链表转化为数组，从而实现随机访问

为了首尾取节点，使用双指针法遍历数组，当数组中只剩下一个元素时，需要单独处理，防止重复加入，并且最后需要将链表尾置空，这样才能成为一个真正的新链表

知道上述这些细节之后，接下来的工作就是模拟插入的过程

执行流程

  1. 判断链表是否为空，为空不用处理
  2. 将链表转化为数组
  3. 新链表中插入一个节点，方便后续操作
  4. 剩下的节点依次从头尾各取一个插入新链表中
  5. 判断是不是有一个单独的节点需要处理，防止重复加入
  6. 链表尾部置空

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
public:
    void reorderList(ListNode* head) {
        if(head==nullptr)
            return;
        //到这里链表中至少有一个节点
        vector<ListNode*> node;
        //将链表转化为vector，这样就可以随机访问
        while(head!=nullptr){
            node.push_back(head);
            head=head->next;
        }
        int i=1,j=node.size()-1;
        ListNode *temp=new ListNode(0);
        head=node[0];//先加入一个节点
        temp=head;
        while(i<j){
            temp->next=node[j];
            temp=temp->next;
            temp->next=node[i];
            temp=temp->next;
            i++;
            j--;
        }
        if(i==j){
            temp->next=node[i];
            temp=temp->next;
        }
        //不要忘记链表的尾部置空
        temp->next=nullptr;
    }
};

总结

重点是模拟插入的过程，不能出现空指针，并且head的位置不能变，所以需要加入一个新指针辅助节点的插入，并且需要先加入一个节点，方便统一后面节点的插入过程，以新增一个虚拟头结点是一样的道理