Leetcode 206 Reverse Linked List and 92 Reverse Linked List II

Leetcode 206 Reverse Linked List and 92 Reverse Linked List II

Leetcode 206 Reverse Linked List

The problem description is as follow:

Reverse a singly linked list:
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

This problem is basic, thus we should try to solve it in various ways. I tried iteratively and recursively.

Iterative Approach
Edit Reverse Linked List on GitHub

public class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null || head.next == null) 
            return head;
     
        ListNode p1 = head;
        ListNode p2 = head.next;
     
        head.next = null;
        while(p1!= null && p2!= null){
            ListNode temp = p2.next;
            p2.next = p1;
            p1 = p2;
            p2 = temp;
        }
     
        return p1;
    }
}

The time complexity is O(n), we simply traverse the while linked list.

Recursive Approach
Edit Reverse Linked List on GitHub

public class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null || head.next == null)
            return head;
     
        //get second node    
        ListNode second = head.next;
        //set first's next to be null
        head.next = null;
     
        ListNode rest = reverseList(second);
        second.next = head;
     
        return rest;
    }
}

Leetcode 92 Reverse Linked List II

Edit Reverse Linked List II on GitHub

The problem description is as follow:

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:
The definition of linked list is same as previous problem.
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

This problem is mostly the same as previous. The only thing we have to keep aware is to do it in-place and in one-pass. We just have to:

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;
    }
}