Skip to content

Latest commit

 

History

History
144 lines (112 loc) · 3.64 KB

92.reverse-linked-list-ii.md

File metadata and controls

144 lines (112 loc) · 3.64 KB

题目地址

https://leetcode.com/problems/reverse-linked-list-ii/description/

题目描述

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4 Output: 1->4->3->2->5->NULL

思路

考虑取出需要反转的这一小段链表,反转完后再插入到原先的链表中。

以本题为例:

变换的是2,3,4这三个点,那么我们可以先取出2,用front指针指向2,然后当取出3的时候,我们把3加到2的前面,把front指针前移到3,依次类推,到4后停止,这样我们得到一个新链表4->3->2, front指针指向4。

对于原链表来说,有两个点的位置很重要,需要用指针记录下来,分别是1和5,把新链表插入的时候需要这两个点的位置。

用pre指针记录1的位置

当4结点被取走后,5的位置需要记下来

这样我们就可以把倒置后的那一小段链表加入到原链表中

92.reverse-linked-list-ii

(图片来自: https://github.com/MisterBooo/LeetCodeAnimation)

关键点解析

  • 链表的基本操作(交换)
  • 虚拟节点dummy 简化操作
  • 考虑特殊情况 m 是 1 或者 n是链表长度的情况
  • 用四个变量记录特殊节点, 然后操作这四个节点使之按照一定方式连接即可。
    let midStartNode = null;
    let preMidStartNode = null;
    let midEndNode = null;
    let postMidEndNode = null;
  • 注意更新current和pre的位置, 否则有可能出现溢出

代码

/*
 * @lc app=leetcode id=92 lang=javascript
 *
 * [92] Reverse Linked List II
 *
 * https://leetcode.com/problems/reverse-linked-list-ii/description/
 *
 * algorithms
 * Medium (34.13%)
 * Total Accepted:    182.3K
 * Total Submissions: 532.8K
 * Testcase Example:  '[1,2,3,4,5]\n2\n4'
 *
 * Reverse a linked list from position m to n. Do it in one-pass.
 * 
 * Note: 1 ≤ m ≤ n ≤ length of list.
 * 
 * Example:
 * 
 * 
 * Input: 1->2->3->4->5->NULL, m = 2, n = 4
 * Output: 1->4->3->2->5->NULL
 * 
 * 
 */
/**
 * 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) {
    // 虚拟节点,简化操作
    const dummyHead = {
        next: head
    }

    let current = dummyHead.next; // 当前遍历的节点
    let pre = current; // 因为要反转,因此我们需要记住前一个节点
    let index = 0; // 链表索引,用来判断是否是特殊位置(头尾位置)

    // 上面提到的四个特殊节点
    let midStartNode = null;
    let preMidStartNode = null;
    let midEndNode = null;
    let postMidEndNode = null;

    while(current) {
        const next = current.next;
        index++;

        // 对 (m - n) 范围内的节点进行反转
        if (index > m && index <= n) {           
            current.next = pre;
        }

        // 下面四个if都是边界, 用于更新四个特殊节点的值
        if (index === m - 1) {
            preMidStartNode = current;
        }
        if (index === m) {
            midStartNode = current;
        }

        if (index === n + 1) {
            postMidEndNode = current;
        }

        if (index === n) {
            midEndNode = current;;
        }

        pre = current;

        current = next;
    }

    // 两个链表合并起来
    (preMidStartNode || dummyHead).next = midEndNode; // 特殊情况需要考虑
    midStartNode.next = postMidEndNode;

    return dummyHead.next;
};