Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Problem Challenge 1: Reverse alternating K-element Sub-list (medium)

Problem Statement

Given the head of a LinkedList and a number k, reverse every alternating k sized sub-list starting from the head.

The first k nodes are reversed, the next k are left alone, the next k are reversed, and so on. If the last group holds fewer than k nodes, treat it the same way as a full group: reverse it if it falls on a reversing turn, leave it alone if it falls on a skipping turn.

Example:

Input:  1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> null,  k = 3
Output: 3 -> 2 -> 1 -> 4 -> 5 -> 6 -> 9 -> 8 -> 7 -> 10 -> null

.....

.....

.....

Like the course? Get enrolled and start learning!
Sajid Khan

Sajid Khan

· 6 days ago

class Solution {
  reverse(head, k) {
    const dummy = new Node(-1, head);
    let current = dummy;

    while (current.next) {
      const next = current.next;
      const last = this.getNode(current, k);
      const prev = last.next;

      last.next = null;
      current.next = this.reverseList(current.next, prev);

      current = this.getNode(next, k);
    }

    return dummy.next;
  }

  reverseList(node, prev) {
    while (node) {
      const next = node.next;
      node.next = prev;
      prev = node;
      node = next;
    }

    return prev;
  }

  getNode(head, position) {
    while (head && head.next && position > 0) {
      head = head.next;
      position--;
    }

    return head;
  }
}
D

dos

· a month ago

Why my saved code just disappeared ? seems you have TTL for the code submitted. is there any way to restore ?

Show 1 reply
Shaho Shahbazpanahi

Shaho Shahbazpanahi

· a year ago

For this input [1,2,3,4,5,6,7,8,9,10,11] and k= 3, then expected output should be [3,2,1,6, 5, 4,10, 8,9,11, 10] while the solution give us [3,2,1,6, 5, 4,10, 8,9, 10, 11] , the problem stats if the rest of lis is smaller than k, revese it to .

Show 1 reply
L

Lucas

· 4 years ago

Here is my solution! Hope it doesnt crack under pressure :) Image

Reading Progress

0%

Vote for new content