javascript实现单链表的部分反转

题目描述

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

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

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

解答：
本题有可能存在换头的问题，比如题目的第二个例子，所以函数应该返回调整后的新头节点，整个处理过程如下：
1、先判断是否满足 1 <= from <= to <= N,如果不满足，则直接返回原来的头节点
2、找到第from - 1个节点fPre,和第to + 1个节点 fPos. fPre即是要反转部分的前一个节点。fPos是反转部分的后一个节点。把反转的部分先反转，然后正确地链接fPre和 fPos.
例如：1 -> 2 -> 3 -> 4 -> NULL，假设fPre为节点1，fPos为节点4，要反转部分为2 -> 3。先反转成3->2,然后fPre连向即诶单3，节点2连向fPos，就变成了 1 -> 3 -> 2 -> 4 -> NULL.
3, 如果fPre为NULL,说明反转部分是包含头节点的，则返回新的头节点，也就是没反转之前反转部分的最后一个节点，也是反转之后反转部分的第一个节点。如果fPre不为null，则返回旧的头节点。全部过程代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * 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 len = 0, node1 = head, fPre = null, fPos = null;
    while (ndoe1 !== null) {
        fPre = m - 1 === len ? node1 : fPre;
        fPos = n + 1 === len ? node1 : fPos;
        node1 = node1.next;
    }

    if (m > n || m < 1 || n > len) return head;
    node1 = fPre == null ? head : fPre.next;
    let node2 = node1.next;
    node1.next = fPos;
    let next = null;
    while (node2 !== fPos) {
        next = node2.next;
        node2.next =  node1;
        nod1 = node2;
        node2 = next;
    }

    if (fPre !== null) {
        fPre.next = node1;
        return headl
    }
    return node1;
}