重排链表

导航

143. 重排链表LeetCode 一、示例如下：二、思路：三、代码如下：

---

143. 重排链表LeetCode

       给定一个单链表 L：$L_0\to L_1\to \dots \to L_{n-1}\to L_n$ ，将其重新排列后变为： $L\to L_n\to L_1\to L_{n-1}\to L_2\to L_{n-2}\to$…        你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

---

一、示例如下：

给定链表 1->2->3->4, 重新排列为 1->4->2->3. 给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

---

二、思路：

    我们容易发现，我们应该将链表中的节点从中间分开，然后将右侧部分反过来先输出左侧的链表一个节点，然后再紧跟一个右侧的逆置的链表节点。输出结果就是我们要的链表。这里我们将两个链表不是输出而是将他们俩合并即可。步骤如下：         1.寻找链表中点：                在此步骤中我们采用双指针的方法来寻找中间的节点。                双指针也就是快慢指针，开始的时候两个指针都指向链表头部，快的指针一次向后移动两个位置，慢的移动一个位置。这样当快指针移动到链表结尾时候，慢的指针所在的位置就是链表中间的位置。

node getMiddle(node head){ node a = head , b = head; while(b -> next != NULL && b -> next -> next != NULL){ a = a -> next; b = b -> next -> next; } return a; }

        2.链表逆序 ：                链表逆置时候我们也采用双指针法：

node reverse(node head){ node slow = NULL , quick = head; while(quick != NULL){ node temp = quick -> next; quick -> next = slow; slow = quick; quick = temp; } return slow; }

        3.合并链表                两个链表合并在这里就很简单，因为我们从中间分割的链表，所以说两个链表的长度之差不会超过1；

void mergeList(node L1 , node L2){ node L1_temp , L2_temp; while(L1 != NULL && L2 != NULL){ L1_temp = L1 -> next; L2_temp = L2 -> next; L1 -> next = L2; L1 = L1_temp; L2 -> next = L1; L2 = L2_temp; } }

三、代码如下：

#include<bits/stdc++.h> using namespace std; typedef struct Node{ int data; Node *next; }*node; void insert(node &head , int data){ if(head == NULL){ head = new Node(); head->data = data; head->next = NULL; return; } insert(head->next , data); } void mergeList(node L1 , node L2){ node L1_temp , L2_temp; while(L1 != NULL && L2 != NULL){ L1_temp = L1 -> next; L2_temp = L2 -> next; L1 -> next = L2; L1 = L1_temp; L2 -> next = L1; L2 = L2_temp; } } node reverce(node head){ node a = NULL , b = head; while(b != NULL){ node p = b->next; b->next = a; a = b; b = p; } return a; } node getM(node head){ node a = head , b = head; while(b->next != NULL && b->next->next != NULL){ a = a->next; b = b->next->next; } return a; } int main(){ int n , d; cin >> n; node head = NULL; while(n--){ cin >> d; insert(head , d); } node middle = getM(head); node l1 = head; node l2 = NULL; l2 = reverce(middle->next); middle->next = NULL; mergeList(l1 , l2); node f = l1; while(f != NULL){ cout << f->data << " " ; f = f->next; } } 感谢阅读