【链表】 Reverse Linked List II

时间:2022-09-20 19:48:08

题目:

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

For example:
Given 1->2->3->4->5->NULLm = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given mn satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

思路:

找到m节点,从节点m到n依次反转指针,然后把翻转后的串连起来即可

/**
 * 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) {
    if(head==null){
        return head;
    }
    
    var p=head,mpre=null;
    var tempHead=new ListNode(0);
    tempHead.next=head;
    mpre=tempHead;
    for(var i=1;i<m;i++){
        mpre=p;
        p=p.next;
    }
    
    var pre=null,cur=null,next=null;
    var tempp=p;
    for(var i = 1; i <= n-m; i++){//反转m到n的指针
        pre = p;
        cur = p.next;
        next = cur.next;
        cur.next = pre;
        p=cur;
    }
    mpre.next=p;
    tempp.next=next;
    head=tempHead.next;
    tempHead=null;
    return head;
};