将给定的单链表
： 
重新排序为：
要求使用原地算法，不能只改变节点内部的值，需要对实际的节点进行交换。
数据范围：链表长度
，链表中每个节点的值满足 
重新排序为：
要求使用原地算法，不能只改变节点内部的值，需要对实际的节点进行交换。
数据范围：链表长度
要求：空间复杂度 )
并在链表上进行操作而不新建链表，时间复杂度 %20)
进阶：空间复杂度 %20)
， 时间复杂度
[编程题]重排链表
//方法一：使用双端队列import java.util.Deque; import java.util.LinkedList; public class Solution { public void reorderList(ListNode head) { Deque<ListNode> list = new LinkedList<>(); ListNode cur = head; while (cur != null) { list.add(cur); cur = cur.next; } boolean flag = true; while (list.size() > 0) { if (flag) { list.pollFirst().next = list.peekLast(); flag = false; } else { list.pollLast().next = list.peekFirst(); flag = true; } } } }
// 方法二：使用快慢指针+反转链表
public class Solution {
public void reorderList(ListNode head) {
if (head == null)
return;
ListNode p1 = head;
ListNode p2 = head.next;
//快慢指针
while (p2 != null && p2.next != null) {
p1 = p1.next;
p2 = p2.next.next;
}
ListNode reverse = null;
if (p2 == null) {
reverse = reverse(p1.next);
p1.next = null;
} else {
reverse = reverse(p1);
p1.next = null;
}
ListNode cur1 = head;
ListNode cur2 = reverse;
while (cur1 != null && cur2 != null) {
ListNode oldNext1 = cur1.next;
ListNode oldNext2 = cur2.next;
cur1.next = cur2;
cur2.next = oldNext1;
cur1 = oldNext1;
cur2 = oldNext2;
}
}
//反转链表
private ListNode reverse(ListNode h) {
ListNode p = h;
ListNode pre = null;
while (p != null) {
ListNode oldNext = p.next;
p.next = pre;
pre = p;
p = oldNext;
}
return pre;
}
}
发表于 2021-12-06 10:10:27
回复(0)
const int N = 1e4;
typedef struct ListNode* NodePtr;
void reorderList(NodePtr head ) {
// corrner case
if (!head || !head->next) return;
NodePtr stk[N];
int top = -1;
NodePtr slow = head, fast = head;
while (fast && fast->next) {
*(stk + ++top) = slow;
slow = slow->next;
fast = fast->next->next;
}
NodePtr p, q = fast ? slow->next : slow, nxt;
while (top >= 0) {
p = *(stk + top--);
nxt = q->next;
q->next = p->next;
p->next = q;
q = nxt;
}
slow->next = NULL;
}
发表于 2021-09-24 17:14:22
回复(0)
function reorderList( head ) {
// write code here
if(!head) return
let a=[]
while(head){
a.push(head)
head=head.next
}
let len=Math.floor(a.length/2)
for(let j=0;j<len;j++){
a[j].next=a[a.length-1-j]
a[a.length-1-j].next=a[j+1]
}
a[len].next=null
return a[0]
}
module.exports = {
reorderList : reorderList
};
// write code here
if(!head) return
let a=[]
while(head){
a.push(head)
head=head.next
}
let len=Math.floor(a.length/2)
for(let j=0;j<len;j++){
a[j].next=a[a.length-1-j]
a[a.length-1-j].next=a[j+1]
}
a[len].next=null
return a[0]
}
module.exports = {
reorderList : reorderList
};
发表于 2021-08-19 13:54:17
回复(0)
分三步进行：
- 寻找链表中点
- 链表逆序
- 合并链表
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ import java.util.*; public class Solution { public void reorderList(ListNode head) { if (head == null || head.next == null) return; // 寻找链表中点 ListNode mid = middleNode(head); ListNode l1 = head; ListNode l2 = mid.next; mid.next = null; // 链表逆序 l2 = reverseList(l2); // 合并链表 mergeList(l1, l2); } public ListNode middleNode(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast.next!= null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode cur = head; while (cur != null) { ListNode tmp = cur.next; cur.next = pre; pre = cur; cur = tmp; } return pre; } public void mergeList(ListNode l1, ListNode l2) { ListNode l1_tmp; ListNode l2_tmp; while (l1 != null && l2 != null) { l1_tmp = l1.next; l2_tmp = l2.next; l1.next = l2; l1 = l1_tmp; l2.next = l1; l2 = l2_tmp; } } }
发表于 2021-07-31 15:58:34
回复(0)
采用双端队列：
void reorderList(ListNode *head) {
if (head == NULL) return;
deque<ListNode*> que;
ListNode* p = head->next;
while (p) {
que.push_back(p);
p = p->next;
}
ListNode* tmp = head;
tmp->next = NULL;
head = tmp;
while (que.size()>1) {
ListNode* f = que.front();
ListNode* r = que.back();
f->next = NULL;
r->next = NULL;
tmp->next = r;
tmp = tmp->next;
tmp->next = f;
tmp = tmp->next;
que.pop_front();
que.pop_back();
}
if (que.size()==1) {
ListNode* f = que.front();
f->next = NULL;
tmp->next = f;
que.pop_front();
}
}
发表于 2021-05-12 11:20:36
回复(0)
public void reorderList(ListNode head) {
if(head==null||head.next==null) return;
ListNode pre=null;
ListNode p=head;
while(p.next!=null&&p.next.next!=null){
ListNode q=p.next;
while(q.next!=null){
pre=q;
q=q.next;//找到最后一个
}
pre.next=null;//截断
q.next=p.next;//将q插入p之后
p.next=q;
p=p.next.next;//连跳两下
}
}
发表于 2021-04-02 10:50:38
回复(0)
一种很菜的思路：先将尾节点保存，然后删除，最后将尾节点插入到第二个位置，并将第二个位置的下一个节点当成下次执行时的头节点。
不知道是不是原地算法。
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public void reorderList(ListNode head) {
while(head != null && head.next != null && head.next.next != null){
//获取尾节点last
ListNode last = head;
while(last.next != null){
last = last.next;
}
//获取倒数第二个节点secondLast
ListNode secondLast = head;
while(secondLast.next.next != null){
secondLast = secondLast.next;
}
//删除尾节点
secondLast.next = null;
//将原尾节点插入第二个节点
ListNode preNode = head;
ListNode nextNode = head.next;
preNode.next = last;
last.next = nextNode;
//递归继续执行，此时的head为插入节点的下一个节点
head = last.next;
}
}
}
发表于 2020-06-12 18:21:10
回复(0)
class Solution {
ListNode* Rerverse(ListNode*pHead){
ListNode*tail=pHead;
while(tail->next)tail=tail->next;
while(pHead!=tail){
ListNode*temp=pHead->next;
pHead->next=tail->next;
tail->next=pHead;
pHead=temp;
}
return tail;
}
public:
void reorderList(ListNode *head) {
if(!head||!head->next)return ; //必须考虑到只有一个节点和空节点的情况
ListNode*fast=head,*slow=head;
while(fast->next&&fast->next->next){ //快慢指针求中间节点
slow=slow->next;
fast=fast->next->next;
}
ListNode*pHead=slow->next;
slow->next=nullptr;
ListNode*p2=Rerverse(pHead); //翻转列表 尾插法
ListNode*p1=head;
while(p2){
ListNode*p=p1->next;
p1->next=p2;
ListNode*pp=p2->next;
p2->next=p;
p1=p;
p2=pp;
}
}
};
发表于 2020-03-11 11:58:02
回复(0)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void reorderList(ListNode *head) {
if(!head) return;
// 快慢指针找到中间节点
ListNode* fast = head;
ListNode* slow = head;
while(fast->next != NULL && fast->next->next != NULL){
fast = fast->next->next;
slow = slow->next;
}
// 拆分链表，并反转中间节点之后的链表
ListNode* after = slow->next;
slow->next = NULL;
ListNode* pre = NULL;
while(after != NULL){
ListNode* temp = after->next;
after->next = pre;
pre = after;
after = temp;
}
// 合并两个链表
ListNode* first = head;
after = pre;
while(first != NULL && after != NULL){
ListNode* ftemp = first->next;
ListNode* aftemp = after->next;
first->next = after;
first = ftemp;
after->next = first;
after = aftemp;
}
}
};
编辑于 2020-03-08 19:33:28
回复(0)
解题思路
①找到中间节点
②将链表拆分并逆序后半部分 ③重新间隔拼接在一起
public class Solution {
public void reorderList(ListNode head) {
//链表长度小于2时直接返回
if(head == null || head.next == null) {
return;
}
//设置两个快慢指针
ListNode slow = head;
ListNode fast = head;
//fast走两步同时slow只走一步，从而找到中间节点
while (fast.next != null && fast.next.next != null){
fast = fast.next.next;
slow = slow.next;
}
//将链表从slow处拆开
ListNode after = slow.next;
slow.next = null;
//将后半部分链表逆序
ListNode pre = null;
while (after != null){
ListNode temp = after.next;
after.next = pre;
pre = after;
after = temp;
}
//将pre链表间隔插入head链表
ListNode first = head;
ListNode second = pre;
while (first != null && second != null){
ListNode firstTemp = first.next;
ListNode secondTemp = second.next;
first.next = second;
first = firstTemp;
second.next = first;
second = secondTemp;
}
}
}
编辑于 2020-02-28 01:56:17
回复(0)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
public:
void reorderList(ListNode *head) {
if(head==NULL||head->next==NULL||head->next->next==NULL)
return ;
ListNode g=ListNode(0);
ListNode *h=&g;
ListNode *hh=h;
int num=0;
ListNode *temp=head;
while(temp!=NULL){
num++;
temp=temp->next;
}
int n=num/2;
temp=head;
ListNode * other=NULL;
for(int i=0;i<n;i++){
temp=temp->next;
}
other=temp;
int t=0;
if(num%2!=0)t=1;
for(int i=0;i<n;i++){
ListNode * curl=head;
head=head->next;
h->next=curl;
curl->next=NULL;
h=h->next;
temp=other;
int o=n+t-1-i;
while(o--){
temp=temp->next;
}
h->next=temp;
h=h->next;
temp->next=NULL;
}
if(t){
temp->next=other;
other->next=NULL;
}
head=hh->next;
return ;
}
};
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
找到链表中间的节点，利用for循环定位计数，创建一个虚拟节点连接新的链表，空间复杂度O（1），并且不改变原节点数据
class Solution {public:
void reorderList(ListNode *head) {
if(head==NULL||head->next==NULL||head->next->next==NULL)
return ;
ListNode g=ListNode(0);
ListNode *h=&g;
ListNode *hh=h;
int num=0;
ListNode *temp=head;
while(temp!=NULL){
num++;
temp=temp->next;
}
int n=num/2;
temp=head;
ListNode * other=NULL;
for(int i=0;i<n;i++){
temp=temp->next;
}
other=temp;
int t=0;
if(num%2!=0)t=1;
for(int i=0;i<n;i++){
ListNode * curl=head;
head=head->next;
h->next=curl;
curl->next=NULL;
h=h->next;
temp=other;
int o=n+t-1-i;
while(o--){
temp=temp->next;
}
h->next=temp;
h=h->next;
temp->next=NULL;
}
if(t){
temp->next=other;
other->next=NULL;
}
head=hh->next;
return ;
}
};
发表于 2020-02-05 18:47:47
回复(0)
public void Solution(ListNode head){
if(head == null) return;
ListNode lowNode = head;
ListNode fastNode = head;
while(fastNode.next != null && fastNode.next.next != null){
lowNode = lowNode.next;
fastNode = fastNode.next.next;
}
ListNode leftNode = head;
ListNode rightNode = lowNode.next;
// 切断中间链
lowNode.next = null;
ListNode p = new ListNode(-1);
ListNode returnNode = p;
// head是左链头 rightNode是右链头
while(leftNode != null){
p.next = leftNode;
leftNode = leftNode.next;
ListNode tempR = rightNode;
while (tempR != null && tempR.next!= null && tempR.next.next!=null){
tempR = tempR.next;
}
if(tempR == null || tempR.next == null){
p.next.next = tempR;
rightNode = null;
}else{
p.next.next = tempR.next;
tempR.next = null;
}
if(p.next != null){
p = p.next.next;
}
}
head = returnNode;
} 思路和归并排序类似：
观察发现该结果是类似二路归并（L0->Ln/2 与 Ln/2+1 -> Ln<逆序>）
故原地排序方法为：
1.找到中间节点 左链表 leftNode 右链表 rightNode（Ln/2+1）
2.每次取一个左链表头，取一个右链表尾
3.取完右链表值后，将其父节点的next索引置空
发表于 2020-01-08 20:18:59
回复(0)
主要知识点：快慢指针寻找链表中点，链表反转，链表合并
import java.util.List;
import java.util.Stack;
/*
将给定的单链表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,2,3,4}，将其重新排序为{1,4,2,3}.
*/
public class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null)
return;
// 快慢指针找到中间节点
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//拆分链表，并反转中间节点之后的链表
ListNode curNode = slow.next; //定义一个辅助curNode
slow.next = null; //将原来的链表拆分，拆分后的最后一个非空节点为slow
ListNode preNode = null; //定义一个空的preNode，表示curNode之前的节点
while (curNode != null) {
ListNode nextNode = curNode.next; //
curNode.next = preNode; //当前节点的下一个节点指向前面的节点，即指针反转
preNode = curNode; //preNode后移到curNode上
curNode = nextNode; //curNode后移
}
//执行完反转操作之后，反转链表的第一个节点为preNode
//合并两个链表
ListNode first = head; //first指向第一个链表的头结点
ListNode after = preNode; //after指向第二个反转后的链表的头结点
while (first != null && after != null) {
ListNode firstTemp = first.next;
ListNode afterTemp = after.next;
first.next = after; //将after的第一个数放在first后面
first = firstTemp; //first后移到firstTemp
after.next = first; //after指向新的first
after = afterTemp; //after后移到afterTemp
}
}
}
发表于 2020-01-06 14:45:39
回复(0)
public class Solution {
// 快慢指针寻找链表中点
private static ListNode findMid(ListNode head){
ListNode quick = head;
ListNode slow = head;
while(quick.next!=null && quick.next.next!=null){
quick = quick.next.next;
slow = slow.next;
}
return slow;
}
// 链表反转
private static ListNode reverse(ListNode head){
ListNode rhead = null;
ListNode cur = head;
while(cur!=null){
ListNode tmp = cur;
cur = cur.next;
tmp.next = rhead;
rhead = tmp;
}
return rhead;
}
public void reorderList(ListNode head) {
if(head==null||head.next==null) return;
// 找到中点后将链表分为两部分，后面一部分反转
ListNode mid = findMid(head);
ListNode rhead = reverse(mid.next);
mid.next = null;
ListNode p = head;
ListNode q = rhead;
// 将两截链表按照p0->q0->p1->q1...重新连接
while(p!=null&&q!=null){
ListNode a = p.next;
ListNode b = q.next;
p.next = q;
q.next = a;
p = a;
q = b;
}
}
}
发表于 2019-12-30 16:25:31
回复(0)
/** 递归思想
每一次将链表尾结点取出，插入至当前链表的头结点之后
对插入结点之后的链表（即原链表的第二个结点之后的子链表）重复上述操作
完成排序
*/
public class Solution {
public void reorderList(ListNode head) {
if(head!=null && head.next!=null){
ListNode tail;
for(tail=head;tail.next.next!=null;tail=tail.next);
ListNode p=tail.next;
tail.next=null;
p.next=head.next;
head.next=p;
reorderList(p.next);
}
}
}
发表于 2019-11-21 11:27:13
回复(0)
public class Solution {
public void reorderList(ListNode head) {
if(head != null && head.next != null){
//快慢指针找到中间节点rightHead
ListNode p1 = head, p2 = head;
while(p2.next != null && p2.next.next != null){
p1 = p1.next;
p2 = p2.next.next;
}
ListNode rightHead = p1.next;
p1.next = null;
//将右边链表逆序翻转
p1 = rightHead.next;
rightHead.next = null;
while(p1 != null){
p2 = p1.next;
p1.next = rightHead;
rightHead = p1;
p1 = p2;
}
//leftHead 和 rightHead 拼接
ListNode leftHead = head;
while(rightHead != null){
ListNode rightNext = rightHead.next, leftNext = leftHead.next;
leftHead.next = rightHead;
leftHead.next.next = leftNext;
leftHead = leftNext;
rightHead = rightNext;
}
}
}
}
发表于 2019-10-05 15:20:31
回复(0)
emmm就是把最后一个节点往插呗 简单粗暴
终止条件需要判断一下。优点是代码短，缺点是复杂度有点不妥
第一次做题一开始没考虑空链表的情况 以后注意（这让我回想到为什么我蓝桥杯明明自己运行的很好但是最后竟然没得奖）
看到很多大佬用三步走的办法 等会学习一下
感觉用队列和栈也可以做 等会也试试
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void reorderList(ListNode *head) {
if(head==nullptr||head->next==nullptr||head->next->next==nullptr)
return ;
ListNode *p,*m,*q;
p = head;
m = p;
q = m;
while(p->next!=m && p->next!=nullptr){
m = head->next;
while(m->next->next!=nullptr){
m = m->next;
}
q = m->next;
m->next = NULL;
q->next = p->next;
p->next = q;
p = q->next;
}
return ;
}
};
//解法二来啦 就是中间-翻转-合并
class Solution {
public:
void reorderList(ListNode *head) {
if(head==nullptr||head->next==nullptr||head->next->next==nullptr)
return ;
ListNode *slow,*fast;//中间
slow = head;
fast = head;
while(fast->next!=nullptr&&fast->next->next!=nullptr) {// 这个判断注意顺序，一个next要写在两个next之前
slow = slow->next;
fast = fast->next->next;
}
//printf("%d\n",slow->data);
ListNode *m,*p;//翻转
m = slow->next;
while(m->next!=nullptr){
p = m->next;
m->next = p->next;
p->next = slow->next;
slow->next = p;
}
ListNode *se,*fi,*tem;//合并
se = slow->next;
fi = head;
slow->next = nullptr;
while(fi!=NULL&&se!=nullptr){
tem = se;
se = se->next;
tem->next = fi->next;
fi->next = tem;
fi = fi->next->next;
}
}
};
编辑于 2019-09-24 20:31:51
回复(0)
Good Taste Code
class Solution {
public:
void reorderList(ListNode *head) {
if (head == NULL || head->next == NULL || head->next->next == NULL)
return;
ListNode** left = &head;
ListNode** right = left;
while (*left != NULL && (*left)->next != NULL) {
while (*right != NULL && (*right)->next != NULL) {
right = &(*right)->next;
}
ListNode* tail = *right;
*right = NULL;
tail->next = (*left)->next;
(*left)->next = tail;
left = &(*left)->next->next;
right = left;
}
return;
}
};
发表于 2019-08-24 10:23:00
回复(0)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
// 快慢指针拆分链表
ListNode* cutList(ListNode* head){
// 定义快慢指针
ListNode* slow = head;
ListNode* fast = head->next;
// 快慢指针进行更新
while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;
}
// 切断链表并返回
ListNode* temp = slow->next;
slow->next = nullptr;
return temp;
}
// 链表翻转
ListNode* reverse(ListNode* head){
// 特殊情况判断
if (!head || !head->next){
return head;
}
// 定义头结点、三指针
ListNode* prehead = new ListNode(0);
prehead->next = head;
ListNode *last = prehead, *current = head, *next = head->next;
// 开始进行翻转
while(current){
current->next = last;
last = current;
current = next;
next = (next) ? next->next : nullptr;
}
// 进行后处理并返回
head->next = nullptr;
return last;
}
void relink(ListNode* head, ListNode* mid){
ListNode *point_1 = head, *point_2 = mid;
while(point_1){
// 声明寄存器
ListNode* temp = point_1->next;
// 修改point_1指针
point_1->next = point_2;
point_1 = temp;
// 判出
if (!point_2)
break;
// 修改point_2指针
temp = point_2->next;
point_2->next = point_1;
point_2 = temp;
}
}
public:
void reorderList(ListNode *head) {
if (!head || !head->next){
return ;
}
// 切分list
ListNode* mid = cutList(head);
// 逆序第二个list
mid = reverse(mid);
// 重新连接list
relink(head, mid);
}
};
三步走，每步拆分成为一个函数方便封装：（1-2-3-4-5）
1、双指针拆分链表（1-2-3 4-5）
2、将后半段逆序（1-2-3 5-4）
3、交叉拼接链表（1-5-2-4-3）
空间复杂度：O(1)
时间复杂度：O(2.5*n) ~ O(n)
编辑于 2019-08-14 20:33:36
回复(0)
void reorderList(ListNode *head) {
if (head==NULL || head->next==NULL || head->next->next ==NULL)
{
return;
}
ListNode* ptr =head->next;
vector<ListNode*>List;
while (ptr!=NULL)
{
List.push_back(ptr);
ptr=ptr->next;
}
ListNode* ptr_pre =head;
ptr=head->next;
int list_sz =List.size();
for (int i=0;i<list_sz/2;i++)
{
ListNode* insert_node =List.back();
ptr_pre->next=insert_node;
insert_node->next=ptr;
ptr_pre=ptr;
if(((i==list_sz/2 -1) && (list_sz%2!=0))||(i<list_sz/2-1))
{
ptr=ptr->next;
}
List.pop_back();
}
ptr->next=NULL;
}
发表于 2019-06-08 21:26:06
回复(0)
问题信息
难度：
383条回答
782收藏
43569浏览
通过挑战的用户
-
2023-02-01 10:58:44
-
2022-12-16 22:20:45
-
2022-12-01 12:44:29
-
2022-11-15 15:17:13 -
2022-10-10 22:19:02
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
