Cracking the coding interview solutions - Linked Lists
Single linked list implementation
package main
import (
"fmt"
)
type Node struct {
data interface{}
next *Node
}
type LinkedList interface {
size() int
show()
appendData(data interface{}) *Node
removeData(data interface{}) *Node
}
func (node *Node) size() int {
size := 0
n := node
for n != nil {
size++
n = n.next
}
return size
}
func (node *Node) show() {
n := node
for n.next != nil {
fmt.Printf("%v->", n)
n = n.next
}
fmt.Printf("%v\n", n)
}
func (node *Node) appendData(data interface{}) *Node {
n := node
for n.next != nil {
n = n.next
}
n.next = NewNode(data)
return node
}
func (node *Node) removeData(data interface{}) *Node {
if node.data == data {
node = node.next
return node
}
n := node
for n.next != nil {
if n.next.data == data {
n.next = n.next.next
break
}
n = n.next
}
return node
}
func NewNode(data interface{}) *Node {
node := &Node{}
node.data = data
node.next = nil
return node
}
// main ...
func main() {
var list LinkedList
head := NewNode(1)
list = head
list.appendData(2)
list.show()
list.removeData(2)
list.show()
fmt.Println("list size", list.size())
}Write Code to remove duplicates from unordered linked list
Using a hash table to store the data to compare
package main
import (
"fmt"
)
type Node struct {
data interface{}
next *Node
}
type LinkedList interface {
show()
appendData(data interface{}) *Node
removeDuplicates() *Node
}
func (node *Node) appendData(data interface{}) *Node {
n := node
for n.next != nil {
n = n.next
}
n.next = NewNode(data)
return node
}
// removeDuplicates ...
func (node *Node) removeDuplicates() *Node {
uniqueValues := make(map[interface{}]bool)
n := node
uniqueValues[n.data] = true
for n.next != nil {
if uniqueValues[n.next.data] == true {
n.next = n.next.next
} else {
uniqueValues[n.next.data] = true
n = n.next
}
}
return node
}
func (node *Node) show() {
n := node
for n.next != nil {
fmt.Printf("%v->", n)
n = n.next
}
fmt.Printf("%v\n", n)
}
func NewNode(data interface{}) *Node {
node := &Node{}
node.data = data
node.next = nil
return node
}
// main ...
func main() {
var list LinkedList
head := NewNode(2)
list = head
list.appendData(2)
list.appendData(6)
list.show()
list.removeDuplicates()
list.show()
}Without using any extra space
package main
import (
"fmt"
)
type Node struct {
data interface{}
next *Node
}
type LinkedList interface {
show()
appendData(data interface{}) *Node
removeDuplicates() *Node
}
func (node *Node) appendData(data interface{}) *Node {
n := node
for n.next != nil {
n = n.next
}
n.next = NewNode(data)
return node
}
// removeDuplicates ...
func (node *Node) removeDuplicates() *Node {
n := node
for n != nil {
runner := n
for runner.next != nil {
if runner.next.data == n.data {
runner.next = runner.next.next
} else {
runner = runner.next
}
}
n = n.next
}
return node
}
func (node *Node) show() {
n := node
for n.next != nil {
fmt.Printf("%v->", n)
n = n.next
}
fmt.Printf("%v\n", n)
}
func NewNode(data interface{}) *Node {
node := &Node{}
node.data = data
node.next = nil
return node
}
// main ...
func main() {
var list LinkedList
head := NewNode(2)
list = head
list.appendData(2)
list.appendData(2)
list.show()
list.removeDuplicates()
list.show()
}Write an algorithm to find the kth to last element of a singly linked list
Recursive Method - recursively go through all nodes and print where we are at kth from last
package main
import (
"fmt"
)
type Node struct {
data interface{}
next *Node
}
type LinkedList interface {
show()
appendData(data interface{}) *Node
}
func (node *Node) appendData(data interface{}) *Node {
n := node
for n.next != nil {
n = n.next
}
n.next = NewNode(data)
return node
}
func (node *Node) show() {
n := node
for n.next != nil {
fmt.Printf("%v->", n)
n = n.next
}
fmt.Printf("%v\n", n)
}
func NewNode(data interface{}) *Node {
node := &Node{}
node.data = data
node.next = nil
return node
}
// kthToLast ...
func kthToLast(head *Node, k int) int {
if head == nil {
return 0
}
index := kthToLast(head.next, k) + 1
if index == k {
fmt.Printf("%v to last is %v", k, head)
}
return index
}
// main ...
func main() {
var list LinkedList
head := NewNode(1)
list = head
list.appendData(4)
list.appendData(9)
list.show()
kthToLast(head, 2)
}Iterative Method - we will have two pointers, p1 and p2. we will move p1 k depth inside then we will run both in sync, when p1 hit end of list p2 will be at the kth from last
package main
import (
"fmt"
)
type Node struct {
data interface{}
next *Node
}
type LinkedList interface {
show()
appendData(data interface{}) *Node
}
func (node *Node) appendData(data interface{}) *Node {
n := node
for n.next != nil {
n = n.next
}
n.next = NewNode(data)
return node
}
func (node *Node) show() {
n := node
for n.next != nil {
fmt.Printf("%v->", n)
n = n.next
}
fmt.Printf("%v\n", n)
}
func NewNode(data interface{}) *Node {
node := &Node{}
node.data = data
node.next = nil
return node
}
// kthToLast ...
func kthToLast(head *Node, k int) interface{} {
p1 := head
p2 := head
for i := 1; i < k; i++ {
p1 = p1.next
}
for p1.next != nil {
p1 = p1.next
p2 = p2.next
}
return p2
}
// main ...
func main() {
var list LinkedList
head := NewNode(1)
list = head
list.appendData(4)
list.appendData(9)
list.show()
fmt.Printf("%v to last is node %v", 1, kthToLast(head, 1))
}Given a singly linked list, delete the middle node (not necessary be midddle), given only access to that node
we will copy the data of next node the given node and delete the next node by pointing to next of next node
package main
import (
"fmt"
)
type Node struct {
data interface{}
next *Node
}
type LinkedList interface {
show()
appendData(data interface{}) *Node
}
func (node *Node) appendData(data interface{}) *Node {
n := node
for n.next != nil {
n = n.next
}
newNode := NewNode(data)
n.next = newNode
return newNode
}
func (node *Node) show() {
n := node
for n.next != nil {
fmt.Printf("%v->", n)
n = n.next
}
fmt.Printf("%v\n", n)
}
func NewNode(data interface{}) *Node {
node := &Node{}
node.data = data
node.next = nil
return node
}
// deleteGivenNode ...
func deleteGivenNode(node *Node) {
node.data = node.next.data
node.next = node.next.next
}
// main ...
func main() {
var list LinkedList
head := NewNode(1)
list = head
node1 := list.appendData(4)
list.appendData(9)
list.show()
deleteGivenNode(node1)
list.show()
}Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x. order of appearance does not matter.
we will iterate from head and push values less than x to head and leave values greater than or equal to x at there place
package main
import (
"fmt"
)
type Node struct {
data int
next *Node
}
type LinkedList interface {
show()
appendData(data int) *Node
}
func (node *Node) appendData(data int) *Node {
n := node
for n.next != nil {
n = n.next
}
newNode := NewNode(data)
n.next = newNode
return newNode
}
func (node *Node) show() {
n := node
for n.next != nil {
fmt.Printf("%v->", n)
n = n.next
}
fmt.Printf("%v\n", n)
}
func NewNode(data int) *Node {
node := &Node{}
node.data = data
node.next = nil
return node
}
func partitionList(node *Node, partitionValue int) *Node {
head := node
tail := node
for node != nil {
next := node.next // very important
if node.data < partitionValue {
node.next = head
head = node
} else {
tail.next = node
tail = node
}
node = next
}
tail.next = nil
return head
}
// main ...
func main() {
var list LinkedList
head := NewNode(3)
list = head
list.appendData(5)
list.appendData(8)
list.appendData(5)
list.appendData(10)
list.appendData(2)
list.appendData(1)
fmt.Println("given linked list")
list.show()
newHead := partitionList(head, 5)
list = newHead
fmt.Println("partitioned linked list")
list.show()
}You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
example - (7->1->6) + (5->9->2) = (2->1->9) we can convert linked lists to numbers and add then return a linked list out of that number. But it is not the one that this question wants you to do. Other way is to recursively go through both linked lists and sum the respective digits and carry forward the 1 or 0 depending on the sum value
Digits are in backward order
package main
import (
"fmt"
)
type Node struct {
data int
next *Node
}
type LinkedList interface {
show()
appendNode(node *Node) *Node
appendData(data int) *Node
}
func (node *Node) appendData(data int) *Node {
n := node
for n.next != nil {
n = n.next
}
newNode := NewNode(data)
n.next = newNode
return n
}
func (node *Node) appendNode(newNode *Node) *Node {
n := node
for n.next != nil {
n = n.next
}
n.next = newNode
return n
}
func (node *Node) show() {
n := node
for n.next != nil {
fmt.Printf("%v->", n)
n = n.next
}
fmt.Printf("%v\n", n)
}
func NewNode(data int) *Node {
node := &Node{}
node.data = data
node.next = nil
return node
}
func sumLists(l1 *Node, l2 *Node, carry int) *Node {
if l1 == nil && l2 == nil {
return nil
}
value := carry
if l1 != nil {
value += l1.data
}
if l2 != nil {
value += l2.data
}
result := NewNode(value % 10)
if (l1 != nil && l1.next != nil) || (l2 != nil && l2.next != nil) {
if value >= 10 {
carry = 1
} else {
carry = 0
}
more := sumLists(l1.next, l2.next, carry)
result.appendNode(more)
} else {
result = NewNode(value)
}
return result
}
// main ...
func main() {
var l1, l2, l3 LinkedList
head1 := NewNode(7)
l1 = head1
l1.appendData(1)
l1.appendData(6)
l1.appendData(3)
head2 := NewNode(5)
l2 = head2
l2.appendData(9)
l2.appendData(2)
l2.appendData(5)
fmt.Println("given linked list 1")
l1.show()
fmt.Println("given linked list 2")
l2.show()
result := sumLists(head1, head2, 0)
l3 = result
fmt.Println("sum linked list")
l3.show()
}FollowUp - What if digits in linked list are in forward order
package main
import (
"fmt"
)
var l1, l2, l3 LinkedList
type Node struct {
data int
next *Node
}
type LinkedList interface {
show()
size() int
appendNode(node *Node) *Node
appendData(data int) *Node
}
func (node *Node) size() int {
size := 0
n := node
for n != nil {
size++
n = n.next
}
return size
}
func (node *Node) appendData(data int) *Node {
n := node
for n.next != nil {
n = n.next
}
newNode := NewNode(data)
n.next = newNode
return n
}
func (node *Node) appendNode(newNode *Node) *Node {
n := node
for n.next != nil {
n = n.next
}
n.next = newNode
return n
}
func (node *Node) show() {
n := node
for n.next != nil {
fmt.Printf("%v->", n)
n = n.next
}
fmt.Printf("%v\n", n)
}
func NewNode(data int) *Node {
node := &Node{}
node.data = data
node.next = nil
return node
}
type sum struct {
sum *Node
carry int
}
func appendBefore(head *Node, data int) *Node {
node := NewNode(data)
node.next = head
return node
}
func getValue(n1 *Node, n2 *Node) *sum {
if n1 == nil && n2 == nil {
sum := sum{}
return &sum
}
sum := getValue(n1.next, n2.next)
value := sum.carry + n1.data + n2.data
result := appendBefore(sum.sum, value % 10)
sum.sum = result
sum.carry = value / 10
return sum
}
func paddList(head *Node, padding int) *Node {
node := head
for i := 0; i < padding; i++ {
node = appendBefore(head, 0)
}
return node
}
func sumLists(n1 *Node, n2 *Node) *Node {
l1 := n1
l2 := n2
len1 := l1.size()
len2 := l2.size()
if len1 < len2 {
n1 = paddList(n1, len2 - len1)
}
if len2 < len1 {
n2 = paddList(n2, len1 - len2)
}
sum := getValue(n1, n2)
if sum.carry == 0 {
return sum.sum
} else {
return appendBefore(sum.sum, sum.carry)
}
}
// main ...
func main() {
head1 := NewNode(7)
l1 = head1
l1.appendData(1)
l1.appendData(6)
l1.appendData(3)
head2 := NewNode(5)
l2 = head2
l2.appendData(9)
l2.appendData(2)
fmt.Println("given linked list 1")
l1.show()
fmt.Println("given linked list 2")
l2.show()
result := sumLists(head1, head2)
l3 = result
fmt.Println("sum linked list")
l3.show()
}Implement a function to check if a linked list is a palindrome
we take two pointer equal to head and make one pointer to go twice than one other. When fast pointer reach end, other one will be in middle. We start from head and middle pointer simultaneosly and compare values.