一、题目描述
题目链接: . - 力扣(LeetCode)
二、解题思路
一定要注意给分开之后的两个链表的末尾节点 .next 置为 null,否则会出错(超出时间限制)!
三、代码
class Solution {
public void reorderList(ListNode head) {
if(head == null || head.next == null || head.next.next == null) {
return;
}
//1、找到链表的中间节点
ListNode slow = head, fast = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
//此时slow所指即为中间节点
//将原始链表分为两个链表,要注意给分开之后的两个链表的末尾节点.next置为空
//2、逆序slow之后的部分(双指针)
ListNode prev = slow.next;
slow.next = null;
ListNode cur = prev.next;
prev.next = null;
while(cur != null) {
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
//逆序之后,prev指向逆序后链表的首节点
//3、合并两个链表
ListNode cur1 = head, cur2 = prev;
ListNode ret = new ListNode(0);
ListNode ccur = ret;
while(cur1 != null) {
ccur.next = cur1;
ccur = cur1;
cur1 = cur1.next;
if(cur2 != null) {
ccur.next = cur2;
ccur = cur2;
cur2 = cur2.next;
}
}
}
}