【算法题】链表重排(js)

发布时间:2023年12月25日

力扣链接:https://leetcode.cn/problems/LGjMqU/description/
在这里插入图片描述

/**
 * 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.
 */
// 算法:将链表一分为2,将第二段链表反转,然后第一段链表和第二段链表交叉合并
var reorderList = function (head) {
    // 双指针快慢法寻找中间节点
    let slow = head
    let fast = head
    while (fast.next && fast.next.next) {
        slow = slow.next
        fast = fast.next.next
    }
    // 将中间节点的下一节点作为第二段节点的头节点
    let scondList = slow.next
    //断开与第二条链表的链接
    slow.next = null

    // 反转第二条链表
    let pre = null
    let cur = scondList
    while (cur) {
        let temp = cur.next
        cur.next = pre
        pre = cur
        cur = temp
    }
    // 更新第二条链表
    scondList = pre
    //合并链表
    let first = head
    let second = scondList
    while (second) {
        const temp1 = first.next
        const temp2 = second.next
        first.next = second;
        second.next = temp1
        first = temp1
        second = temp2
    }
};
文章来源:https://blog.csdn.net/qq_43682422/article/details/135206803
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。