Single linked list trick collection

February 4, 2023

Name: Moch Lutfi
Twitter: @kaptenupi

Reverse

When we need to process data from tail to head, so we need to read reverse data flow backward because we cannot going back directly using single linked list.

// Singly-linked lists are already defined with this interface:
// type ListNode struct {
//   Value interface{}
//   Next *ListNode
// }
func reverse(head *ListNode) *ListNode {
	var prev *ListNode
	current := head
	for current != nil {
		next := current.Next
		current.Next = prev
		prev = current
		current = next
	}
	return prev
}

Merge 2 linked list

Recursive approach

func solution(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    
    if l2 == nil {
        return l1
    }
    
    if l1.Value.(int) <= l2.Value.(int) {
        l1.Next = solution(l1.Next, l2)
        return l1
    } else {
        l2.Next = solution(l1, l2.Next)
        return l2
    }
}

Iterative

// Singly-linked lists are already defined with this interface:
// type ListNode struct {
//   Value interface{}
//   Next *ListNode
// }
//
func solution(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy:=&ListNode{}
    current := dummy
    for {
        if (l1 == nil) {
            current.Next = l2;
            break;
        }
        if (l2 == nil) {
            current.Next = l1;
            break;
        }
 
        /* Compare the data of the two
        lists whichever lists' data is
        smaller, append it into tail and
        advance the head to the next Node
        */
        if (l1.Value.(int) <= l2.Value.(int)) {
            current.Next = l1;
            l1 = l1.Next;
        }else {
            current.Next = l2;
            l2 = l2.Next;
        }
		current = current.Next
	}
    return dummy.Next
}

Word Boggle kthSmallestInBST