92. Reverse Linked List II

最后更新

二刷。

这个题挺难的啊。。

首先找到需要翻转的位置。

有prev和temp两个node，思路是把范围内的node放到prev和temp之间。。

这里的temp其实是翻转区间的尾端，用tail表示。

所以prev和tail这2个NODE是指着不动的。

首先找到下一个塞入他们之间的node：
next = tail.next;

记录下下个要塞入他们之间的node:
tail.next = next.next;

塞入：
next.next = tail;
prev.next = next;

public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null || head.next == null || m == n) return head;
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode temp = head;
        
        for (int i = 1; i < m; i++) {
            temp = temp.next;
            prev = prev.next;
        }
        
        ListNode break1 = prev;
        
        for (int i = 0; i < n - m; i++) {
            ListNode next = temp.next;
            temp.next = next.next;
            next.next = prev.next;
            prev.next = next;
        }

        return dummy.next;
    }
}

一刷

调转序列中的一段

逻辑上没什么难的

从左往右调转的话

记录当前的下一个tempNext
记录最后的下一个endNext
记录当前最后的下一个tempEnd
当前的下一个指向最后的下一个 temp.next = tempEnd
当前最后的下一个变为当前的下一个 tempEnd = temp.next

（break 如果当前的下一个 = 最后的下一个) tempNexit == endNext

当前 = 当前的下一个 temp = temp.next

最后弄完尾部是处理好的
TEMP是指向掉调转序列的第一个

然后处理首部

2种情况一开始找M N的时候要记录begin 就是m的上一个 begin开始是HEAD

最后看看BEGIN是不是=HEAD 等于的话整个数列是从头开始调转的直接返还TEMP
否则 begin = temp
return head

public ListNode reverseBetween(ListNode head, int m, int n) 
    {
        if(head == null || n==m) return head;
        
        ListNode cur = head;
        ListNode begin = cur;
        boolean moved = false;
        for(int i = 1; i < m;i++)
        {
            begin = cur;
            cur = cur.next;
            moved = true;
        }

        ListNode start = cur;
        for(int i = 0; i < (n-m);i++)
        {
            cur = cur.next;
        }

        ListNode con = cur.next;
        ListNode end = cur.next;
        ListNode temp = start;
        ListNode tempNext = temp.next;
        
        while(true)
        {
            tempNext = temp.next;
            temp.next = con;
            con= temp;
            if(tempNext == end) break;
            temp = tempNext;
        }
        
        if(moved)
        {
            begin.next = temp;
            return head;
        }
        else
        {
            return temp;
        }
        
        
    }

感觉没什么好办法。。难在EDGE CASE的解决

二刷。

。。感觉没什么套路，就是楞做。。

这次的方法是，移动M个找到开始的地方。

然后转M-N次。

弄一下开头结尾。。

返还。

public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) 
    {
        if( head == null || m == n || head.next == null) return head;
        
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        
        int diff = n - m;
        ListNode temp = dummy;
        int total = m-1;
        while(total != 0)
        {
            temp = temp.next;
            total--;
        }
        
        ListNode tempHead = temp;
        ListNode tempTail = temp.next;
        
        temp = temp.next;
        ListNode next = temp.next;
        for(int i = 0 ; i < n-m ;i++)
        {
            ListNode prev = temp;
            temp = next;
            next = next.next;
            
            temp.next = prev;
            
        }
        
        tempHead.next.next = next;
        tempHead.next = temp;
        return dummy.next;
    }
}