leetcode143重排链表
程序员文章站
2024-02-04 08:26:46
...
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.
输入示例:
5
1 2 3 4 5
输出示例:
head–>1–>5–>2–>4–>3–>tail
思路:看了题解
1.找中间位置,快慢指针思想吧,p走一步q走两步,当q走到链表末尾的时候p恰好在中间位置。
2.逆置后半部分链表(实质上用的是头插法逆置)
3.将逆置后的尾部依次插入前半部分链表(直白写法)
代码:
#include<iostream>
using namespace std;
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) {}
};
ListNode *createByTail()
{
ListNode *head;
ListNode *p1,*p2;
int n=0,num;
int len;
cin>>len;
head=NULL;
while(n<len && cin>>num)
{
p1=new ListNode(num);
n=n+1;
if(n==1)
head=p1;
else
p2->next=p1;
p2=p1;
}
return head;
}
void displayLink(ListNode *head)
{
ListNode *p;
p=head;
cout<<"head-->";
while(p!= NULL)
{
cout<<p->val<<"-->";
p=p->next;
}
cout<<"tail\n";
}
class Solution {
public:
void reorderList(ListNode* head) {
ListNode *p=head,*q=head,*r;
if(!head)
return ;
while(q->next)//找中间结点
{
p=p->next;
q=q->next;
if(q->next)
q=q->next;
}
q=p->next;
p->next=nullptr;
while(q)//逆置后半部分
{
r=q->next;
q->next=p->next;
p->next=q;
q=r;
}
q=p->next;
p->next=nullptr;
p=head;
while(q)//将逆置后的后半部分链表插入到前边
{
r=q->next;
q->next=p->next;
p->next=q;
p=q->next;
q=r;
}
}
};
int main()
{
ListNode* head = createByTail();
Solution().reorderList(head);
displayLink(head);
return 0;
}
DHU给了输入输出代码 存一下。
小坑:写第一个p->next=null的时候晕了,写成p=null…一直报错 无语了 细心点。
上一篇: rapidjson
下一篇: C语言之assert(断言)与防御式编程
推荐阅读
-
DHU-高级程序语言设计链表基础9长整数加法运算
-
leetcode143重排链表
-
已知链表A和B分别表示两个集合,其元素递增排列。请设计一个算法,用于求出A与B的交集,并存放于A链表中。
-
(4)已知两个链表A和B分别表示两个集合,其元素递增排列。请设计算法求出两个集合A和B 的差集(即仅由在A中出现而不在B中出现的元素所构成的集合),并以同样的形式存储,同时返回该集合的元素个数。
-
单链表的九种基本操作(2021.5)
-
通过一趟遍历确定单链表中值最大的结点
-
已知两个链表A和B分别表示两个集合,其元素递增排列。请设计算法求出A与B的交集,并存放于A链表中。
-
单链表简单操作
-
删除单链表中大于mink且小于maxk的所有元素结点
-
已知两个单链表A和B分别表示两个集合,其元素递增排列。请设计一个算法,用于求出A和B的交集,并存放于A链表中。