Reverse Linked List II (0092/Medium)

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given1->2->3->4->5->NULL,m= 2 andn= 4,

return1->4->3->2->5->NULL.

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

Two phase Java solution:

First while loop moves cur to index = m;

Second while loop conduct a normal LinkedList reverse.

public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head == null) return null;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy, cur = head;
        int k = 1;

        while(cur.next != null && k != m){
            cur = cur.next;
            pre = pre.next;
            k++;
        }

        while(cur.next != null && k != n){
            ListNode preNext = pre.next;
            pre.next = cur.next;
            ListNode next = cur.next;
            cur.next = next.next;
            next.next = preNext;
            k++;
        }

        return dummy.next;
    }


1. Traverse to the reverse starting point
2. Do the in-place reverse exactly the same as previous, iteratively or recursively as you like
3. While doing reverse, keep track of the reverse starting point and ending point so 
    we can link the reversed part of list to the rest part



public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode helper = new ListNode(0);
        helper.next = head;
        ListNode p = helper;
        for(int i = 1; i < m; i++)
            p = p.next;

        p.next = reverse(p.next, n - m + 1);
        return helper.next; 
    }

    private ListNode reverse(ListNode head, int n){
        ListNode node = head, prev = null, next = null;
        for(int i = 0; i < n; i++){
            next = node.next;
            node.next = prev;
            prev = node;
            node = next;
        }
        head.next = node;
        return prev;
    }
}

Reverse Linked List (0206/Easy)

Reverse a singly linked list.

Example:

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode first = head;
        ListNode reverseHead = null; //建立一个新的节点用来存放结果
        while (first != null) { //遍历输入链表，开始处理每一个节点
            ListNode second = first.next; //先处理第一个节点first，所以需要一个指针来存储first的后继
            first.next = reverseHead; //将first放到新链表头节点的头部
            reverseHead = first; //移动新链表的头指针，让它始终指向新链表头部
            first = second; //继续处理原链表的节点，即之前指针存放的后继，循环往复
        }
        return reverseHead;
    }
}


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head; //处理最小输入的情况，即空链表和单节点链表
        ListNode second = head.next; //将即将被调用的下一个节点分离，即将下一个调用的输入存在second里
        ListNode reverseHead = reverseList(second); //将调用后的结果存储，这个结果就是最终结果。之后利用递归，调用刚才存好的输入
        second.next = head; //上面一步的调用已经完成以second为首的链表的反转，所以现在second变成了反转完成后的尾节点
　　　　　　　　　　　　　　　　 //把这个尾节点的next指向一开始输入的前驱，即head，完成整个链表反转
        head.next = null; //最开始的头节点要变成尾节点，即在后面补null使链表终结
        return reverseHead; 
    }
}