Leetcode–Reverse Linked List II

The Problem:

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.

Notes:

  1. Two pointers, record the node pre before m, and link each node between m and n to pre.next.
  2. Attention to null check for p before calling p.next.
  3. Head can change, use a fake head trick.

Java Solution:

/**
 * 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) {
        ListNode fkHead = new ListNode(0);
        fkHead.next = head;
        ListNode p = fkHead;
        int k = m;
        while(k>1){
            k--;
            p = p.next;
        }
        ListNode pre = p;
        p = p.next;
        k = n-m;
        while(k>0 && p.next!=null){ //---!!--be careful to check p.next before access p.next.next
            k--;
            ListNode temp = p.next.next;
            p.next.next = pre.next;
            pre.next = p.next;
            p.next = temp;
        }
        return fkHead.next;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s