25. Reverse Nodes in k-Group

Posted on | Edited on | Views:

LeetCode

Approach: Iteration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head==null||head.next==null||k==1) return head;
        ListNode dummy=new ListNode(-1),begin=dummy;
        dummy.next=head;
        int count=0;
        while(head!=null){
            count++;
            if(count%k==0){
                begin=reverse(begin,head.next);
                head=begin.next;
            }
            else{
                head=head.next;
            }
        }
        return dummy.next;
    }
    public ListNode reverse(ListNode begin, ListNode end){
        ListNode pre=begin, curr=begin.next, start=curr;
        while(curr!=end){
            ListNode next=curr.next;
            curr.next=pre;
            pre=curr;
            curr=next;
        }
        begin.next=pre;
        start.next=curr;
        return start;
    }
}

Approach: Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    private ListNode reverse(ListNode node,int k){
        ListNode newHead=null,ptr=node;
        while(k>0){
            ListNode next=ptr.next;
            ptr.next=newHead;
            newHead=ptr;
            ptr=next;
            k--;
        }
        return newHead;
    }
    public ListNode reverseKGroup(ListNode head, int k) {
        int cnt=0;
        ListNode ptr=head;
        while(cnt<k&&ptr!=null){
            cnt++;ptr=ptr.next;
        }
        if(cnt==k){
            ListNode reverseHead=reverse(head,k);
            head.next=reverseKGroup(ptr,k);
            return reverseHead;
        }
        return head;
    }
}

0%