Reverse Linked List II, Leetcode 解题笔记

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结点。反转的方法就是每读到一个结点,把它插入到m结点前面位置,然后m结点接到读到结点的下一个。总共只需要一次扫描,所以时间是O(n),只需要几个辅助指针,空间是O(1)。

/**
 * 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 dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode post = null;
        ListNode rstart = null;
        ListNode rend = null;
        ListNode cur = null;
        if(head == null || head.next == null) return head;
        
        int count = 1;
    
        while(count < m && pre != null){
            pre = pre.next;
            count++;
        }
        
        rend = pre.next;
        cur = pre.next.next;
        ListNode cur_pre = pre.next;
        count = 1;
        while(count < n-m+1){
            ListNode temp = cur.next;
            cur.next = cur_pre;
            cur_pre = cur;
            cur = temp;
            count++;
        }
        pre.next = cur_pre;
        rend.next = cur;
        return dummy.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