Ray-56/like-algorithms

✅92. 反转链表 II

bazinga-web opened this issue · 2 comments

92. 反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:

1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

解题思路:

  1. 使用 206.反转链表 的方法将 m,n 之间的链表进行反转
  2. 额外定义两个指针分别保存反转后需要链接的位置,将反转后的链表与原链表拼接
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} m
 * @param {number} n
 * @return {ListNode}
 */
var reverseBetween = function(head, m, n) {
    let prev = null;
    let curr = head;

    for (let i = 1; i < m; i++) {
        prev = curr;
        curr = curr.next;
    }

    let prev2 = prev;
    let curr2 = curr;

    for (let i = m; i <= n; i++) {
        [curr.next, prev, curr] = [prev, curr, curr.next]
    }

    if (prev2 !== null) {
        prev2.next = prev;
    } else {
        head = prev;
    }

    curr2.next = curr;
    return head;
};
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} m
 * @param {number} n
 * @return {ListNode}
 */
var reverseBetween = function(head, m, n) {
    let prev = null;
    let curr = head;

    for (let i = 1; i < m; i++) {
        prev = curr;
        curr = curr.next;
    }

    let prev2 = prev;
    let curr2 = curr;

    for (let i = m; i <= n; i++) {
        const next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }

    if (prev2 !== null) {
        prev2.next = prev;
    } else {
        head = prev;
    }
    
    curr2.next = curr;
    return head;
};