东莞网站制作找哪里_有哪些免费的ppt模板下载网站_苏州seo培训_电商网站设计论文

LCR 026.重排链表

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

输入: head = [1,2,3,4]
输出: [1,4,2,3]

输入: head = [1,2,3,4,5]
输出: [1,5,2,4,3]

法1：

分析：

var reorderList = function(head) {let dummy = new ListNode(0);dummy.next = head;        let fast = dummy;let slow = dummy;// 快慢指针，找到链表的中点while (fast !== null && fast.next !== null) {slow = slow.next;fast = fast.next;if (fast.next !== null) {fast = fast.next;}            }// 分割链表并反转后半部分let temp = slow.next;slow.next = null;link(head, reverseList(temp), dummy);
};// 合并两个链表
function link(node1, node2, head) {let prev = head;while (node1 !== null && node2 !== null) {let temp = node1.next;// 交替连接节点prev.next = node1;node1.next = node2;prev = node2;node1 = temp;node2 = node2.next;}// 如果链表1还有剩余，直接连接if (node1 !== null) {prev.next = node1;}
}// 反转链表
function reverseList(first) {let prev = null;let cur = first;let head = null;// 反转链表while (cur !== null) {let next = cur.next;cur.next = prev;if (next === null) {head = cur;}prev = cur;cur = next;}return head;
}// 定义链表节点
function ListNode(val) {this.val = val;this.next = null;
}