Reverse Linked List I&II leetcode

everse a linked list.

Example

For linked list 1->2->3, the reversed linked list is 3->2->1

Challenge

Reverse it in-place and in one-pass

翻转一个list，如果把node的指针指向前一个， 则node.next就没法得到  所以需要使用双指针，

public class Solution {
    /**
     * @param head: The head of linked list.
     * @return: The new head of reversed linked list.
     */
    public ListNode reverse(ListNode head) {
        ListNode prev = null;
        while(head != null){
            ListNode tem = head.next;
            head.next = prev;
            prev = head;
            head = tem;
        }
        return prev;
    }
}

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->NULL, m = 2 and n = 4,

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

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

翻转m--n, 不仅要把m-n转好， preMnode. next 要指向n， m.next 要指向postNnode

public class Solution {
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (m > n || head == null){
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        for (int i = 1; i < m; i++){
            head = head.next;
        }
        ListNode preM = head;
        ListNode mNode = head.next;
        ListNode nNode = mNode;
        ListNode postN = mNode.next;
        for (int i = m; i < n; i++){
            ListNode tem = postN.next;
            postN.next = nNode;
            nNode = postN;
            postN = tem;
        }
        preM.next = nNode;
        mNode.next = postN;
        return dummy.next;
    }
}

更好地解决方法：

维护3个指针，startpoint，node1和node2。

 startpoint永远指向需要开始reverse的点的前一个位置。

 node1指向正序中第一个需要rever的node，node2指向正序中第二个需要reverse的node。 

 交换后，node1 在后，node2在前。这样整个链表就逆序好了。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (m > n || head == null){
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode startpoint = dummy;
        ListNode node1 = null;
        ListNode node2 = null;
        for (int i = 0; i < n; i++){
            if (i < m-1){
                startpoint = startpoint.next;// startpoint 指向m-1点
            } else if (i == m-1){
                node1 = startpoint.next;
                node2 = startpoint.next.next;
            }else{
              node1.next = node2.next;//node1 指向node2的后面
              node2.next= startpoint.next;//node2 放入startpoint后面
              startpoint.next = node2;//同上一行
              node2 = node1.next;// 改变node2变成node1的下一个， 再开始下次以转换
              
            }
            
        }
        return dummy.next;
    }

}