25. Reverse Nodes in k-Group

January 18, 2020

Introduction

I had a mock interview as an interviewee this morning 9:00 AM on Jan. 18, 2020, I was asked to solve the algorithm to reverse a linked list first, I solved using recursive solution, and shared the idea how to solve iterative way; next I was asked to work on reverse a linked list in group.

Case study

I like to work on a test case 1->2->3->4, k = 2, so that I have to work on the algorithm to reverse a linked list, and also I have to make sure that first group 1->2's first node will be connected to next group 3->4's last node which should be the head of reversed linked list.

How to work on it efficiently? I will add more detail later.

C# My first practice in August 2015

Here is the link. 

Jan. 18, 2020

I had a mock interview as an interviewee this morning, I was asked to solve the algorithm to reverse a linked list first, I solved using recursive solution, and shared the idea how to solve iterative way; next I was asked to work on reverse a linked list in group.

Case study

I like to work on a test case 1->2->3->4, k = 2, so that I have to work on the algorithm to reverse a linked list, and also I have to make sure that first group 1->2's first node will be connected to next group 3->4's last node which should be the head of reversed linked list.

How to work on it efficiently? I will add more detail later.

My practice in August 2015

I found the solution I wrote in August 2015.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode ReverseKGroup(ListNode head, int k) {
        if (head == null)
            {
                return null;
            }

            ListNode dummy = new ListNode(0);
            dummy.next = head;
            int count = 0;
            ListNode pre = dummy;
            ListNode cur = head;
            while (cur != null)
            {
                count++;
                ListNode next = cur.next;
                if (count == k)
                {
                    pre = reverse(pre, next);
                    count = 0;
                }
                cur = next;
            }
            return dummy.next;
        }

        private  ListNode reverse(ListNode pre, ListNode end)
        {
            if (pre == null || pre.next == null)
                return pre;

            ListNode head = pre.next;
            ListNode cur = pre.next.next;
            while (cur != end)
            {
                ListNode next = cur.next;
                cur.next = pre.next;
                pre.next = cur;
                cur = next;
            }

            head.next = end;
            return head;
        }  
}