重排链表双指针链表逆置链表合并 143. 重排链表LeetCode

77 阅读 0 评论 51 点赞

我是靠谱客的博主直率学姐，最近开发中收集的这篇文章主要介绍重排链表双指针链表逆置链表合并 143. 重排链表LeetCode ，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

重排链表

143. 重排链表LeetCode

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

一、示例如下：

给定链表 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;
}
}