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
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/2200.html
標籤：其他
上一篇：529.掃雷游戲