反转链表II

来源Leetcode第92题反转链表II

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

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

示例:

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

---

憨批写法

写的时候没考虑到一些特殊条件，用了太多的if了判断特殊情况，但是用时0ms，击败了100% hhh

思路就是找到要交换的部分，然后切开，交换那部分链表，在重新连接即可。

public ListNode reverseBetween(ListNode head, int m, int n) {
    if(head == null || head.next == null || m ==1 && n == 1)
        return head;
    ListNode p1 = head;
    int i = 1;
    while(i < m - 1){
        //找到前一个结点
        p1 = p1.next;
        i++;
    }
    ListNode p2 = p1.next;
    i++;
    while(i < n){
        //找到末尾结点
        p2 = p2.next;
        i++;
    }
    ListNode newHead,newCur;
    if(m == 1)
        newHead = head;
    else newHead = p1.next;
    newCur = p2;
    p2 = p2.next;
    newCur.next = null;
    newCur = null;
    if(m != 1)
    p1.next = null;
    while(newHead != null){
        ListNode temp = newHead.next;
        newHead.next = newCur;
        newCur = newHead;
        newHead = temp;
    }
    if(m == 1)
        p1 = newCur;
    else
        p1.next = newCur;
    while(newCur.next != null)
        newCur = newCur.next;
    newCur.next = p2;
    if(m == 1)
        return p1;
    return head;
}

简洁

在题解里找到了一个写的相对比较简洁的代码，思路大概是差不多的

    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode tail = head;  // tail 记录首个需要翻转的节点
        ListNode pre = head;   // pre 记录首个需要翻转的节点的前一个节点

        for(int i=1; i<m; ++i) // 用 pre 记录翻转序列的前一个节点, tail 记录翻转序列的头一个节点
        {
            pre = tail;
            tail = tail.next;
        }

        n -= m; // 新的 n 记录需要翻转的次数
        ListNode sub_head = tail;  // 记录需翻转的字串的头节点

        while(n-- != 0){ // 翻转子串
            ListNode h = tail.next;
            tail.next = h.next;
            h.next = sub_head;
            sub_head = h;
            if(m != 1) // 若不是从第一个节点就开始翻转,则进行子串头节点的拼接操作
                pre.next = sub_head;
        }

        if(m != 1) // 若不是从首节点开始翻转,直接返回原头结点
            return head;
        return sub_head; // 否则表示从首节点开始翻转,返回新的头结点
}