Lexi's Leetcode solutions

[leetcode] Reverse Nodes in k-Group | 把链表按k个一组反转

Posted on: August 13, 2013

keep 3个pointer:

  • prevStart:要reverse的section的前一个节点
  • start:section第一个
  • end:section最后一个

然后就每次reverse好了section,和prevStart连上就行了,然后prevStart 越过k个,接着做。这是个练习linked list的好题。

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode prevStart = dummy;
    while (prevStart != null) {
        ListNode start = prevStart.next;
        ListNode end = prevStart;
        for (int i = 0; i < k; i++) {
            end = end.next;
            if (end == null)
                return dummy.next;
        }
        prevStart.next = reverse(start, end);
        for (int i = 0; i < k; i++) {
            prevStart = prevStart.next;
        }
    }
    return dummy.next;
}
private ListNode reverse(ListNode start, ListNode end) {
    ListNode prev = start;
    ListNode curr = start.next;// want to make curr point to prev
    ListNode afterEnd = end.next;
    while (curr != afterEnd) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    start.next = afterEnd;
    return end;
}

 

Tags:

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

Blog Stats

  • 222,234 hits
August 2013
M T W T F S S
 1234
567891011
12131415161718
19202122232425
262728293031  
%d bloggers like this: