1. 题目描述
给定一个单链表 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.
2. 实现思路
这个题目可以使用快慢指针来实现,具体实现思路如下:
- 首先使用快慢两个指针,获取链表的中点
- 从链表的中点断开,慢指针指向前半个链表,快指针指向后半个链表
- 将后半个链表进行翻转,让快指针重新指向翻转后的后半个链表
-
3. 代码实现
/**
* 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 || !head.next) return
let slow = head
let fast = head
// 获取链表的中间节点
while(fast && fast.next){
slow = slow.next
fast = fast.next.next ? fast.next.next : null
}
// 将链表从中点断开,fast指向后半个链表,slow指向前半个链表
fast = slow.next
slow.next = null
slow = head
// 反转链表后半部分
let pre = null
let cur = fast
while(cur){
let temp = cur.next
cur.next = pre
pre = cur
cur = temp
}
// 将fast指向后半段反转后的链表
fast = pre
// 将两个链表按照要求进行合并
while(fast){
let slowNext = slow.next
let fastNext = fast.next
slow.next = fast
fast.next = slowNext
slow = slowNext
fast = fastNext
}
};
4. 提交结果