leetcode 92. Reverse Linked List II

https://leetcode.com/problems/reverse-linked-list-ii/

将链表从m到n的位置反转，链表的位置从1记起，1<=m<=n<=链表长度

一、问题描述

测试用例：

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

要求只进行一遍遍历。

二、代码实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    
    public ListNode reverseBetween3(ListNode head, int m, int n) {
        if (head == null || head.next == null || m == n) {
            return head;
        }
        
        //添加一个伪头节点
        ListNode newHead = new ListNode(-1);
        newHead.next = head;
        ListNode pre1 = newHead, pre2 = newHead;
        // int pos = 1;
        // while (pos < m) {
        //     pre1 = pre1.next;
        //     pre2 = pre2.next;
        //     pos ++;
        // }
        // while (pos < n+1) {
        //     pre2 = pre2.next;
        //     pos ++;
        // }
        for (int i=0; i<m-1; i++) {
            pre1 = pre1.next;
        }
        for (int i=0; i<n; i++) {
            pre2 = pre2.next;
        }
        System.out.println(pre1.val +"   "+ pre2.val);
        
        ListNode temp = reverseList(pre1.next, pre2.next);
        pre1.next = temp;
        
        return newHead.next;
    }
    public ListNode reverseList(ListNode head, ListNode bound) {     
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode cur = head, newBound = bound;
        while (cur.next != bound) {
            //System.out.println(cur.val+"    "+bound.val); //bound可能为null，bound!=null时才可以打印      
            ListNode next = cur.next;
            
            cur.next = newBound;
            newBound = cur;
            
            cur = next;
        }
        cur.next = newBound;
        
        return cur;
    }
    
    public ListNode reverseBetween2(ListNode head, int m, int n) {
        if (head == null || head.next == null || m == n) {
            return head;
        }
        
        //添加一个伪头节点
        ListNode newHead = new ListNode(-1);
        newHead.next = head;
        
        ListNode pre1 = newHead, pre2 = newHead;
        int pos = 1;
        while (pos < m) {
            pre1 = pre1.next;
            pre2 = pre2.next;
            pos ++;
        }
        while (pos < n+1) {
            pre2 = pre2.next;
            pos ++;
        }
        System.out.println(pre1.val +"   "+ pre2.val);
        
        ListNode temp = pre2;
        pre2 = pre2.next;
        temp.next = null;
        temp = reverseList(pre1.next);
        
        pre1.next = temp;
        if (pre2 == null) {
            return newHead.next;
        }
        ListNode cur = temp;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = pre2;
        return newHead.next;
    }
    public ListNode reverseList(ListNode head) {     
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            
            cur.next = pre;
            pre = cur;
            
            cur = next;
        }
        
        return pre;
    }
    
    //[3, 5] 1 2  输出[3]  期待[5, 3]
    public ListNode reverseBetween_error(ListNode head, int m, int n) {
        //[5] 1 1  NullPointerException
        if (head == null || head.next == null) {
            return head;
        }
        
        //[3,5] 2 2  输出[3]  期待[3, 5]
        if (m == n) {
            return head;
        }
        
        ListNode pre = head, next = head;
        int count = 1;
        while (count < m-1) {
            pre = pre.next;
            count++;
        }
        count = 1;
        while (count <= n) {
            next = next.next;
            count++;
        }
        //System.out.println(pre.val +"   "+ next.val);
        
        ListNode cur = pre.next;
        while (cur != next && cur.next != null) {
            ListNode temp = cur.next;
            
            cur.next = next;
            next = cur;
            
            cur = temp;
        }
        pre.next = next;
        
        return head;
    }
    
    public ListNode reverseBetween1(ListNode head, int m, int n) {
        if (head == null || m == n) {
            return head;
        }
        
        if (m == 1) {
            ListNode tempHead = null;
            ListNode pre = null;
            int flag = 1;
            int count = 0;
            while (head != null) {
                ListNode temp = head;
                head = head.next;
                count++;
                
                temp.next = tempHead;
                tempHead = temp;
                if (flag == 1) {
                    pre = tempHead;
                    flag = -flag;
                }
                
                if (count == (n-m+1)) {
                    //null pointer
                    //head = head.next;
                    break;
                }
            }
            
            pre.next = head;
            
            return tempHead;
        }
        
        int count = 1;
        ListNode cur = head;
        ListNode tail = null;
        while (cur != null) {
            if (count == m - 1) {
                tail = cur;
                break;
            }
            cur = cur.next;
            System.out.println(cur.val+"  "+count);
            count++;
            
        }
        //cur is the m-1
        System.out.println(tail.val);
        
        cur = cur.next;
        ListNode tail2 = cur, head2 = cur;
        System.out.println(head2.val+"  "+tail2.val);
        
        cur = cur.next;
        count = 2;
        System.out.println("======================");
        System.out.println(cur.val);
        
        while (cur != null) {
            ListNode temp = cur;
            cur = cur.next;
            
            temp.next = head2;
            tail.next = temp;
            head2 = temp;
            
            
            count++;
            if (count == (n-m+1  +1)) {
                
                break;
            }
            
            System.out.println("hhhhhhhhhhhhh");
        }
        
        //null pointer
        //System.out.println(cur.val);
        
        tail2.next = cur;
        
        return head;
        
    }
}

参考：

https://leetcode.com/problems/reverse-linked-list-ii/discuss/30667/Easy-understanding-java-solution（遍历一遍）

https://leetcode.com/problems/reverse-linked-list-ii/discuss/30672/Python-one-pass-iterative-solution（方法同上）

https://leetcode.com/problems/reverse-linked-list-ii/discuss/30666/Simple-Java-solution-with-clear-explanation（方法同上）

https://leetcode.com/problems/reverse-linked-list-ii/discuss/30668/C%2B%2B-simple