Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Remove Nodes From Linked List

Problem Statement

Given the head node of a singly linked list, modify the list such that any node that has a node with a greater value to its right gets removed. The function should return the head of the modified list.

Examples:

  1. Input: 5 -> 3 -> 7 -> 4 -> 2 -> 1
    Output: 7 -> 4 -> 2 -> 1
    Explanation: 5 and 3 are removed as they have nodes with larger values to their right.

  2. Input: 1 -> 2 -> 3 -> 4 -> 5
    Output: 5
    Explanation: 1, 2, 3, and 4 are removed as they have nodes with larger values to their right.

  3. Input: 5 -> 4 -> 3 -> 2 -> 1

.....

.....

.....

Like the course? Get enrolled and start learning!
Z

zaid

· 3 years ago

I get this error a lot and it doesn't really describe the actual error. Please address this bug

run: line 1: 3 Killed java -cp "./gson-2.9.1.jar:." pkg.MainProd true false Use Example TestcasesRunSubmitPREVIOUS

F

fellainthewagon

· 2 years ago

After reading description the very first thing that came to me is that really easy problem? Then I checked on leetcode and it's medium there.

type Solution struct{}

func (s *Solution) removeNodes(head *ListNode) *ListNode {
    dummy := &ListNode{}
    dummy.Next = head
    
    curr := dummy.Next

    stack := []*ListNode{}
    stack = append(stack, dummy)
    

    for curr != nil && curr.Next != nil {
        next := curr.Next

        for len(stack) != 0 && curr.Val < next.Val {
            prev := stack[len(stack)-1]
            stack = stack[:len(stack)-1]

            prev.Next = next
            curr = prev
        }

        stack = append(stack, curr)
        curr = next
    }

    return dummy.Next
}
Show 1 reply