20201020
给定一个单链表 L:L0→L1→…→Ln-1→Ln , 将其重新排列后变为:L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
思路:
重排后的链表是原链表中间隔插入末尾节点得到:
思路
注意: 翻转后一半链表时会将原链表与后一半链表衔接的 next 指针置为 null 切断链表
抛砖引玉
/**
* 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 == null) return
// 翻转链表
function reverseList(root) {
let _result = null,
node = root
while (node != null) {
// 逐个节点与其next指针上的节点nextTemp交换 -> 翻转链表
let nextTemp = node.next
node.next = _result
_result = node
node = nextTemp
}
return _result
}
let fast = head,
beforeList = head,
afterList = head
// 将afterList指针指向后一半节点
while (fast.next != null && fast.next.next != null) {
afterList = afterList.next
fast = fast.next.next
}
// 注意翻转后一半链表时会将原链表与后一半链表衔接的next指针置为null切断链表
afterList = reverseList(afterList)
let before = null,
after = null
while (beforeList != null && afterList != null) {
before = beforeList.next
after = afterList.next
beforeList.next = afterList
beforeList = before
afterList.next = beforeList
afterList = after
}
return head
}
var reorderList = function(head) {
if (head == null) return
// 存储链表节点
let list = []
while (head !== null) {
let temp = head.next
head.next = null
list.push(head)
head = temp
}
// 按顺序重构next指针
let start = 0,
end = list.length - 1
while (start < end) {
list[start].next = list[end]
// 数组前后两个指针不相邻时构建next
if (end - start != 1) list[end].next = list[start + 1]
start++
end--
}
return list[0]
}
博客: 前端小书童
每天的每日一题,写的题解会同步更新到公众号一天一大 lee 栏目 欢迎关注留言
公众号:前端小书童