将给定的单链表
： 
重新排序为：
要求使用原地算法，不能只改变节点内部的值，需要对实际的节点进行交换。
数据范围：链表长度
，链表中每个节点的值满足 
重新排序为：
要求使用原地算法，不能只改变节点内部的值，需要对实际的节点进行交换。
数据范围：链表长度
要求：空间复杂度 )
并在链表上进行操作而不新建链表，时间复杂度 %20)
进阶：空间复杂度 %20)
， 时间复杂度
[编程题]重排链表
import java.util.*;
/**
* 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) {
ListNode NewHead = head;
List<ListNode> list = new ArrayList<>();
//将所有节点放到集合中
while (NewHead != null) {
list.add(NewHead);
NewHead = NewHead.next;
}
int length = list.size();//节点个数
//如果头节点为null，或者只有一个节点，或者只有两个节点，就不需要转换
if (head == null || length == 1 || length == 2){
return;
}
convert(0, length - 1, list);
}
static void convert(int t, int length, List<ListNode> list) {
int h = length;//集合的总长度
// 1 2 3 4 5 6 7
while (t < length) {
list.get(t).next = list.get(length);
t += 1;
list.get(length).next = list.get(t);
length -= 1;
}
if (h % 2 == 0) {
list.get(h / 2).next = null;
} else {
list.get(h / 2 + 1).next = null;
}
}
}
发表于 2023-11-17 20:37:28
回复(1)
虽然时间有点久但是提供一个思路：
public class Solution {
public void reorderList(ListNode head) {
if(head == null){
return;
}
ListNode temp = head.next;
ListNode p = head;
while (temp != null) {
p.next = pop(p);
if(p.next!=temp){
p.next.next = temp;
}
p = temp;
temp = temp.next;
}
}
public static ListNode pop(ListNode head) {
if (head == null) {
return null;
}
ListNode temp = head;
while (temp.next.next != null) {
temp = temp.next;
}
ListNode result = temp.next;
temp.next = null;
return result;
}
}
发表于 2023-06-10 15:43:26
回复(0)
import java.util.*;
/**
* 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) {
if (head == null) {
return;
}
//保存要添加到链表中间的元素
Stack<Integer> stack = new Stack<>();
//维护最终链表结果的集合
ArrayList<Integer> list = new ArrayList<>();
ListNode tmp = head;
//遍历添加到集合中
while (tmp != null) {
list.add(tmp.val);
tmp = tmp.next;
}
//确定添加到栈的开始位置
int size = 0;
if (list.size() % 2 == 0) {
size = list.size() / 2;
} else {
size = list.size() / 2 + 1;
}
//开始添加到栈
for (int i = size; i < list.size(); i++) {
stack.add(list.get(i));
}
//移除添加到栈的元素
for (int i = size; i < list.size(); i++) {
list.remove(i);
i--;
}
//开始插入
for (int i = 1; i < list.size(); i++) {
list.add(i, stack.pop());
i++;
}
//特殊情况，数组大小为偶数，最后一个在循环无法添加，就在循环结束添加
if (!stack.isEmpty()) {
list.add(stack.pop());
}
//重置链表结构
head=head.next;
for (int i = 1; i < list.size(); i++) {
head.val=list.get(i);
head=head.next;
}
}
}
发表于 2023-05-14 11:50:05
回复(0)
public class Solution {
public void reorderList(ListNode head) {
if ( head == null || head.next == null ) return;
ListNode d = new ListNode(-1);
d.next = head;
// 找中间，断开
ListNode fa = head, sl = head, pre = d;
while ( fa != null && fa.next != null ) {
pre = pre.next;
fa = fa.next.next;
sl = sl.next;
}
pre.next = null;
// 反转
ListNode p = sl, nxt = null;
pre = null;
while ( p != null ) {
nxt = p.next;
p.next = pre;
pre = p;
p = nxt;
}
// 交替插入
p = d.next;
ListNode nxt2 = null;
while ( p != null ) {
nxt = p.next;
p.next = pre;
nxt2 = pre.next;
pre.next = nxt;
p = nxt;
pre = nxt2;
}
// 原链表奇数个节点，特例，将pre接上去
if ( pre != null ) {
p = head;
while ( p.next != null ) {
p = p.next;
}
p.next = pre;
}
}
}
发表于 2023-03-08 16:37:13
回复(0)
public void reorderList(ListNode head) {
Stack<ListNode> stack = new Stack<>();
ListNode p1=head,p2=head;
int cnt=0;
while(p1!=null){
stack.push(p1);
p1=p1.next;
cnt++;
}
for(int i=0;i<cnt/2;i++){
ListNode next = p2.next;
p2.next=stack.pop();
p2.next.next=next;
p2=p2.next.next;
}
if(p2!=null){
p2.next=null;
}
}
发表于 2022-07-03 00:50:49
回复(0)
public static void reorderList1(ListNode head) {
//判断特殊情况，链表长度为0,1,2时，不需要重排，直接返回
if(head==null || head.next==null || head.next.next == null){
return;
}
for(ListNode p = head; p!=null; p=p.next.next){
ListNode a = null;
ListNode b = null;
ListNode q = null;
a = p.next;//a指向p的下一个节点
//再找出倒数第二个节点和最后一个节点
for(ListNode m = a; m!=null; m=m.next){
if(m.next!=null && m.next.next==null){
b = m;
q = m.next;
}
}
p.next = q;
q.next = a;
b.next = null;
if((a==b) || (a.next == b)){
break;
}
}
}
//判断特殊情况，链表长度为0,1,2时，不需要重排，直接返回
if(head==null || head.next==null || head.next.next == null){
return;
}
for(ListNode p = head; p!=null; p=p.next.next){
ListNode a = null;
ListNode b = null;
ListNode q = null;
a = p.next;//a指向p的下一个节点
//再找出倒数第二个节点和最后一个节点
for(ListNode m = a; m!=null; m=m.next){
if(m.next!=null && m.next.next==null){
b = m;
q = m.next;
}
}
p.next = q;
q.next = a;
b.next = null;
if((a==b) || (a.next == b)){
break;
}
}
}
发表于 2022-05-28 11:49:02
回复(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) {
if (head == null) {
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; // 一定不为null
slow.next = null; // 一定要设置为null，为了下方链表重排的结束条件
ListNode pre = slow;
while(after != null) {
ListNode temp = after.next;
after.next = pre;
pre = after;
after = temp;
}
ListNode end = pre;
ListNode start = head;
// 链表重排
while(start != null && end != null) {
ListNode after1 = start.next;
ListNode after2 = end.next;
start.next = end;
end.next = after1;
start = after1;
end = after2;
}
}
}
发表于 2022-02-25 21:11:54
回复(0)
最笨的思路：双指针找到中间节点，截断，后半段链表反转，让后连起来
public class Solution {
public void reorderList(ListNode head) {
ListNode move1 = head;
ListNode move2 = head;
if (head == null || head.next == null || head.next.next == null) {return;}
while (move1.next != null && move1.next.next != null) {
move1 = move1.next.next;
move2 = move2.next;
}
move1 = test(move2.next);
move2.next = null;
move2 = head;
ListNode move3 = null;
while (move2 != null && move1 != null) {
move3 = move2.next;
move2.next = move1;
move2 = move1;
move1 = move3;
}
}
public ListNode test(ListNode head){
ListNode pre = null;
ListNode nex = null;
while (head != null) {
nex = head.next;
head.next = pre;
pre = head;
head = nex;
}
return pre;
}
}
发表于 2022-01-22 22:36:54
回复(0)
public class Solution {
public void reorderList(ListNode head) {
//空间复杂度 O(1) ， 时间复杂度 O(n) 不拆链表
if(head ==null || head.next==null) return ;
ListNode slow = head;
ListNode fast = head;
while(fast.next != null && fast.next.next!=null){//找到链表中点
slow = slow.next;
fast=fast.next.next;
}
fast= slow.next;
//对rigth部分 链表 倒序
ListNode fast_next;
while(fast.next != null){
fast_next=fast.next;
fast.next = fast_next.next;
fast_next.next=slow.next;
slow.next=fast_next;
}
//对链表 右边链表 向左边间隔插入
fast = slow.next;
ListNode cur = head;
while(cur != slow && fast!=null){
slow.next=fast.next;
fast.next =cur.next;
cur.next=fast;
cur =fast.next;
fast=slow.next;
}
}
}
发表于 2022-01-10 15:17:18
回复(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) {
if(head != null)
{
int listLen = getLen(head);
int delIndex = listLen - listLen / 2 - 1;
ListNode p = head;
for(int i = 0; i < delIndex; i++){
p = p.next;
}
// 拆分为两个链表
ListNode head2 = p.next,delNode = null;
head2 = reverseList(head2);
p.next = null;
p = head;
while(head2 != null){
delNode = head2;
head2 = head2.next;
// 开始插入
addNode(p,delNode);
p = p.next.next;
}
}
}
public ListNode reverseList(ListNode head){
ListNode newHead = new ListNode(-1);
ListNode del = null;
while(head != null){
del = head;
head = head.next;
del.next = newHead.next;
newHead.next = del;
}
return newHead.next;
}
public void addNode(ListNode preNo, ListNode addNo){
addNo.next = preNo.next;
preNo.next = addNo;
}
public int getLen(ListNode head){
int len = 0;
while(head != null){
len++;
head = head.next;
}
return len;
}
}
发表于 2021-12-17 16:20:33
回复(0)
public class Solution {
public void reorderList(ListNode head) {
if(head==null) return;
ListNode mid=middle(head);
ListNode ad=mid.next;
ListNode l=head;
//截断
mid.next=null;
ListNode r=reverse(ad);//翻转
merge(l,r);
}
public ListNode middle(ListNode node){
ListNode slow =node;
ListNode fast=node;
while(fast.next!=null&&fast.next.next!=null){
slow=slow.next;
fast=fast.next.next;
}
return slow;
}
public ListNode reverse(ListNode node){
if(node==null) return null;
if(node.next==null) return node;
ListNode no=reverse(node.next);
//与前一个节点连接的过程有两步
node.next.next=node;
node.next=null; //理解这一步? 不然就是相互指向的，此时我们知道node代表的是最后一个节
//因此我们将最后一个节点的next赋值为null. 不然最后的返回也不对呀，是个死循环了。
return no;
}
public void merge(ListNode node1,ListNode node2){
while(node1!=null&&node2!=null){
ListNode l=node1.next;
ListNode r=node2.next;
node1.next=node2;
node1=l;
node2.next=node1;
node2=r;
}
}
}
发表于 2021-12-10 14:13:45
回复(0)
//方法一：使用双端队列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)
问题信息
难度：
76条回答
782收藏
43612浏览
通过挑战的用户
-
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号
