Reorder List (M)
题目
Given a singly linked list L: (L_0→L_1→…→L_{n-1}→L_n),
reorder it to: (L_0→L_n→L_1→L_{n-1}→L_2→L_{n-2}→…)
You may not modify the values in the list's nodes, only nodes itself may be changed.
Example 1:
Given 1->2->3->4, reorder it to 1->4->2->3.
Example 2:
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.
题意
将给定链表按照指定顺序重新排列为新链表。
思路
利用快慢指针找到中间结点,将链表分为左右两部分,将右链表逆序后逐个插入左链表的间隔中。
代码实现
Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
if (head == null) {
return;
}
// 找到中间结点
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode rHead = null;
ListNode p = slow.next;
slow.next = null; // 注意断开左右链表,不然可能生成环
// 逆置右链表
while (p != null) {
ListNode temp = p.next;
p.next = rHead;
rHead = p;
p = temp;
}
// 将逆置后的右链表逐个插入左链表
while (rHead != null) {
ListNode temp = rHead.next;
rHead.next = head.next;
head.next = rHead;
rHead = temp;
head = head.next.next;
}
}
}
JavaScript
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {void} Do not return anything, modify head in-place instead.
*/
var reorderList = function (head) {
if (!head) return
let slow = head
let fast = head
while (fast.next && fast.next.next) {
fast = fast.next.next
slow = slow.next
}
let head2 = null
let cur = slow.next
slow.next = null
while (cur) {
let tmp = cur.next
cur.next = head2
head2 = cur
cur = tmp
}
while (head2) {
let tmp = head2.next
head2.next = head.next
head.next = head2
head = head2.next
head2 = tmp
}
}