前言
中间又断更新。
正文
问题来源
本问题来自leetcode上的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.
分析：
用一个map来记录访问过的节点
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reorderList(head *ListNode) {
for head != nil {
q := head.Next
if q == nil || q.Next == nil {
break
}
for q.Next.Next != nil {
q = q.Next
}
q.Next.Next = head.Next
head.Next = q.Next
q.Next = nil
head = head.Next
if head != nil {
head = head.Next
}
}
}
思路：用快慢双指针遍历链表区分链表的前半部分和后半部分
借鉴LeetCode141——环形链表和LeetCode142——环形链表II中的思路二，我们用快慢双指针遍历链表以区分链表的前半部分和后半部分。参照代码，慢指针cur2移动一步，则快指针cur3移动2步。
以示例1为例（链表中节点个数是偶数个）：-1 -> 1 -> 2 -> 3 -> 4，其中-1是我们设立的虚拟头节点，也是cur2和cur3指针的共同起点。当cur3到达4节点时，遍历结束，此时cur2在2节点，其后半部分节点从cur2.next节点开始。
以示例2为例（链表中节点个数是奇数个）：-1 -> 1 -> 2 -> 3 -> 4 -> 5，其中-1是我们设立的虚拟头节点，也是cur2和cur3指针的共同起点。当cur3到达4节点时，遍历结束，此时cur2在3节点，其后半部分节点也从cur2.next节点开始。
因此无论链表中节点个数的奇偶性，在cur2和cur3移动结束后，其后半部分节点均是从cur2.next节点开始的。
我们将链表分成两部分，第一部分是cur2.next节点之前的节点，第二部分是cur2.next及其之后的节点。
接下来我们只需反转第二部分节点，关于反转链表的方法，可以参考LeetCode206——反转链表，本题的实现中使用了非递归的方式反转链表。
最后，我们只需根据题意，用两部分节点拼接出我们需要的新链表即可。
时间复杂度是O(n)，其中n为链表中的节点个数。空间复杂度是O(1)。
public class Solution {
public void reorderList(ListNode head) {
//设立虚拟头节点
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
//cur1指向链表头节点
ListNode cur1 = head;
//cur2，cur3是快慢双指针，cur2移动一步，cur3移动两步
ListNode cur2 = dummyHead;
ListNode cur3 = dummyHead;
while(cur3 != null && cur3.next != null) {
cur2 = cur2.next;
cur3 = cur3.next.next;
}
cur2 = cur2.next;
//寻找cur2的父节点preCur2
ListNode preCur2 = dummyHead;
while(preCur2.next != cur2) {
preCur2 = preCur2.next;
}
preCur2.next = null;
//反转后半段链表
ListNode newHead = reverseLinkedList(cur2);
ListNode newCur1 = newHead;
//组合出新链表
while(cur1 != null && newCur1 != null) {
ListNode nextCur1 = cur1.next;
ListNode nextNewCur1 = newCur1.next;
cur1.next = newCur1;
newCur1.next = nextCur1;
newCur1 = nextNewCur1;
cur1 = nextCur1;
}
}
private ListNode reverseLinkedList(ListNode head) {
if(head == null || head.next == null) {
return head;
}
ListNode pre = null;
ListNode cur = head;
ListNode next = cur.next;
while(cur != null) {
cur.next = pre;
pre = cur;
cur = next;
if(cur != null) {
next = cur.next;
}
}
return pre;
}
}
总结：
勤思考。
结语
不管怎么样好好加油。
