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

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

示例:

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

这个题因为是从位置m开始反转,所以我们需要m之前的一个节点first,m位置的节点cur(最后需要放置在n位置)。
将cur后面的节点记为next,将cur的next指向next的next,next的next指向first的next,first的next指向next(将3置为first的后继节点);
重复上一步的步骤,将cur后面的节点记为next(此时为4),将cur的next指向next的next,next的next指向first的next,first的next指向next(将4置为first的后继节点);
知道n位置为止。
流程如图(原谅拙劣的手画图、嫌弃电脑画图太麻烦):
拙劣的画图

解法如下:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dhead = new ListNode(-1);
        dhead.next = head;
        
        ListNode first = dhead;
        for(int i=1;i<m;i++){
            first = first.next;
        }
        ListNode cur = first.next;
        for(int i=m;i<n;i++){
            ListNode next = cur.next;
            cur.next = next.next;
            next.next = first.next;
            first.next = next;
        }
        return dhead.next;
    }
}
Last modification:April 30th, 2019 at 03:59 am
大家一起分享知识,分享快乐