题目链接 : https://leetcode-cn.com/problems/reorder-list/
题目描述:
给定一个单链表 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.
思路:
思路一: 栈
想法: 把节点压入栈中, 再弹出来,不就可以实现倒过来了吗?
难点: 弹出多少? 弹出一半? 要考虑!
思路二:
用这方法, 先做一下下面两题
206. 反转链表,这道题是翻转整个链表
92. 反转链表 II,这道题是翻转链表的一部分
接下来, 用图说明方法:
所以,有三步
- 找中点
- 翻转中点之后的链表(好多方法,
Python和Java各用一种) - 依次拼接
代码:
思路一:
class Solution(object):
def reorderList(self, head):
"""
:type head: ListNode
:rtype: None Do not return anything, modify head in-place instead.
"""
if not head: return None
p = head
stack = []
# 把所有节点压入栈中
while p:
stack.append(p)
p = p.next
# 长度
n = len(stack)
# 找到中点前一个位置
count = (n - 1) // 2
p = head
while count:
# 弹出栈顶
tmp = stack.pop()
# 与链头拼接
tmp.next = p.next
p.next = tmp
# 移动一个位置
p = tmp.next
count -= 1
stack.pop().next = None
java
class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null) return;
Deque<ListNode> stack = new LinkedList<>();
ListNode p = head;
while (p != null) {
stack.push(p);
p = p.next;
}
int n = stack.size();
int count = (n - 1) / 2;
p = head;
while (count != 0) {
ListNode tmp = stack.pop();
tmp.next = p.next;
p.next = tmp;
p = tmp.next;
--count;
}
stack.pop().next = null;
}
}
class Solution(object):
def reorderList(self, head):
"""
:type head: ListNode
:rtype: None Do not return anything, modify head in-place instead.
"""
if not head or not head.next: return head
# 1 2 3 4 5
fast = head
pre_mid = head
# 找到中点, 偶数个找到时上界那个
while fast.next and fast.next.next:
pre_mid = pre_mid.next
fast = fast.next.next
# 翻转中点之后的链表,采用是pre, cur双指针方法
pre = None
cur = pre_mid.next
# 1 2 5 4 3
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
# 翻转链表和前面链表拼接
pre_mid.next = pre
# 1 5 2 4 3
# 链表头
p1 = head
# 翻转头
p2 = pre_mid.next
#print(p1.val, p2.val)
while p1 != pre_mid:
# 建议大家这部分画图, 很容易理解
pre_mid.next = p2.next
p2.next = p1.next
p1.next = p2
p1 = p2.next
p2 = pre_mid.next
java
class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null) return;
ListNode slow = head;
ListNode fast = head;
// 找中点 1 2 3 4 5 6
while (fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}
// 翻转中点, 才用插入法 1 2 3 6 5 4
ListNode pre = slow;
ListNode cur = slow.next;
while (cur.next != null){
ListNode tmp = cur.next;
cur.next = tmp.next;
tmp.next = pre.next;
pre.next = tmp;
}
// 拼接 1 6 2 5 3 4
ListNode p1 = head;
ListNode p2 = slow.next;
while (p1 != slow){
// 建议大家这部分画图, 很容易理解的
slow.next = p2.next;
p2.next = p1.next;
p1.next = p2;
p1 = p2.next;
p2 = slow.next;
}
}
}