吹拉弹唱


  • Home
  • Archive
  • Categories
  • Tags
  • Books
  •  

© 2022 Kleon

Theme Typography by Makito

Proudly published with Hexo

Code - Linked List

Posted at 2022-05-05Updated at 2022-05-05 interview  interview algorithm 

  • LeetCode
    • 234. Palindrome Linked List
    • 2. Add Two Numbers
    • 371. Sum of Two Integers
    • 160. Intersection of Two Linked Lists
    • 599. Minimum Index Sum of Two Lists
    • 202. Happy Number
    • 141. Linked List Cycle
    • 142. Linked List Cycle II
    • 206. Reverse Linked List
    • 92. Reverse Linked List II
    • 143. Reorder List
    • 19. Remove Nth Node From End of List
    • 1721. Swapping Nodes in a Linked List
    • 24. Swap Nodes in Pairs
    • 25. Reverse Nodes in k-Group
    • 21. Merge Two Sorted Lists
    • 23. Merge k Sorted Lists
    • 82. Remove Duplicates from Sorted List II

# LeetCode

# 234. Palindrome Linked List

leetcode

If the head pointer is nil, return true.

Solution 1
We could push values into an array and use two pointer sliding from start and end respectively.
Time complexity O(n), space complexity O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
    if head == nil {
        return true
    }
    
    s := []int{}
    for cur := head; cur != nil; cur = cur.Next {
        s = append(s, cur.Val)
    }
    
    for i, j := 0, len(s) - 1; i < j; {
        if s[i] != s[j] {
            return false
        }
        i++
        j--
    }
    return true
}

Solution 2
Reverse the first half of list and compare them.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return true
    }
    isPalindrome := true

    length := 0
    for cur := head; cur != nil; cur = cur.Next {
        length++
    }

    // reverse the first half list
    step := length / 2
    var prev *ListNode
    cur := head
    for i := 1; i <= step; i++ {
        cur.Next, prev, cur = prev, cur, cur.Next
    }
    mid := cur

    var left, right *ListNode = prev, nil
    if length%2 == 0 {
        right = mid
    } else {
        right = mid.Next
    }

    // compare
    for left != nil && right != nil {
        if left.Val != right.Val {
            isPalindrome = false
            break
        }
        left = left.Next
        right = right.Next
    }
    
    // cur = prev
    // prev = mid
    // for cur != nil {
    //     cur.Next, prev, cur = prev, cur, cur.Next
    // }

    return isPalindrome
}

# 2. Add Two Numbers

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    head := &ListNode{}
    current := head
    carry := 0
    for l1 != nil && l2 != nil {
        sum := l1.Val + l2.Val + carry
        if sum >= 10 {
            carry = 1
            sum -= 10
        } else {
            carry = 0
        }
        current.Next = &ListNode{
            Val: sum,
        }
        current = current.Next
        l1 = l1.Next
        l2 = l2.Next
    }
    var p *ListNode
    if l1 != nil {
        p = l1
    } else if l2 != nil {
        p = l2
    }
    
    for p != nil {
        sum := p.Val + carry
        if sum >= 10 {
            carry = 1
            sum -= 10
        } else {
            carry = 0
        }
        current.Next = &ListNode{
            Val: sum,
        }
        current = current.Next
        p = p.Next
    }
    
    if carry == 1 {
        current.Next = &ListNode{
            Val: carry,
        }
    }
    return head.Next
}

Simplified Version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    head := &ListNode{}
    current := head
    carry := 0
    for carry > 0 || l1 != nil || l2 != nil {
        if l1 != nil {
            carry += l1.Val
            l1 = l1.Next
        }
        if l2 != nil {
            carry += l2.Val
            l2 = l2.Next
        }
        current.Next = &ListNode{
            Val: carry % 10,
        }
        carry /= 10
        current = current.Next
    }
    return head.Next
}

# 371. Sum of Two Integers

leetcode

Bit operation, the basic theory of full adder.

1
2
3
4
5
6
7
8
func getSum(a int, b int) int {
  s, c := a^b, a&b
  for c != 0 {
    c = c << 1
    s, c = s^c, s&c
  }
  return s
}

# 160. Intersection of Two Linked Lists

leetcode

Brute Force

Hash Table

Traverse through list a and get d. Traverse through b to check if b is in d.

Concat Two Lists

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil {
        return nil
    }
    a := headA
    b := headB
    for a != b {
        if a == nil {
            a = headB
        } else {
            a = a.Next
        }
        if b == nil {
            b = headA
        } else {
            b = b.Next
        }
    }
    return a
}

# 599. Minimum Index Sum of Two Lists

leetcode

Brute Force

Hash Table

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func findRestaurant(list1 []string, list2 []string) []string {
    hash := make(map[string]int)
    min := math.MaxInt32
    res := []string{}
    for i, word := range list1 {
        hash[word] = i
    }
    for i, word := range list2 {
        if index, exists := hash[word]; exists {
            sum := index + i
            if sum < min {
                min = sum
                res = []string{word}
            } else if sum == min {
                res = append(res, word)
            }
        }
    }
    return res
}

# 202. Happy Number

leetcode

Floyd Cycle Detection Using Two Pointers.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func isHappy(n int) bool {
    slow, fast := n, n
    for {
        slow = digitSquareSum(slow)
        fast = digitSquareSum(digitSquareSum(fast))
        if fast == 1 {
            return true
        }
        if slow == fast {
            break
        }
    }
    return false
}

func digitSquareSum(n int) int {
    sum, tmp := 0, 0
    for n > 0 {
        tmp = n % 10;
        sum += tmp * tmp;
        n /= 10;
    }
    return sum;
}

# 141. Linked List Cycle

leetcode

Two pointers to detect cycle.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        }
    }
    return false
}

# 142. Linked List Cycle II

leetcode

Two pointers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// fast = x + y + n(y + z)
// slow = x + y
// fast = 2slow
// x + y + n(y + z) = 2x + 2y
// y + z = x + y
// x = z
func detectCycle(head *ListNode) *ListNode {
    fast := head
    slow := head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            p1 := fast
            p2 := head
            for p1 != p2 {
                p1 = p1.Next
                p2 = p2.Next
            }
            return p2
        }
    }
    return nil    
}

# 206. Reverse Linked List

leetcode

Two pointer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var pre, tmp *ListNode
    cur := head
    for cur != nil {
        tmp = cur.Next
        cur.Next = pre
        pre = cur
        cur = tmp
    }
    return pre
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var pre *ListNode
    cur := head
    for cur != nil {
        pre, cur, cur.Next = cur, cur.Next, pre
    }
    return pre
}

# 92. Reverse Linked List II

leetcode

Need to think a little bit.

1
vhead head ... last first ... pre cur ...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, left int, right int) *ListNode {
    cur := head
    cnt := 1
    vhead := &ListNode{Next:head}
    last := vhead
    for cnt < left {
        last = cur
        cur = cur.Next
        cnt++
    }
    
    // fmt.Printf("%v\n", cur.Val)
    
    var pre *ListNode
    first := cur
    for cnt <= right {
        pre, cur, cur.Next = cur, cur.Next, pre
        cnt++
    }

    last.Next = pre
    first.Next = cur
    
    return vhead.Next
}

# 143. Reorder List

leetcode

Combination of Reserve List I&II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reorderList(head *ListNode)  {
    // find the middle node
    slow := head
    fast := head
    for fast.Next != nil && fast.Next.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    
    // reverse the second half
    var pre *ListNode
    cur := slow.Next
    for cur != nil {
        pre, cur, cur.Next = cur, cur.Next, pre
    }
    slow.Next = nil
    
    cur1, cur2 := head, pre
    for cur2 != nil {
        cur1.Next, cur1, cur2 = cur2, cur2, cur1.Next
    }
}

# 19. Remove Nth Node From End of List

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    fast, slow := head, head
    for i := 0; i< n; i++ {
        fast = fast.Next
    }
    if fast == nil {
        return head.Next
    }
    for fast.Next != nil {
        fast = fast.Next
        slow = slow.Next
    }
    slow.Next = slow.Next.Next
    return head
}

# 1721. Swapping Nodes in a Linked List

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapNodes(head *ListNode, k int) *ListNode {
    fast, slow := head, head
    for i := 0; i < k - 1; i++ {
        fast = fast.Next
    }
    left := fast
    fast = fast.Next
    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }
    right := slow
    right.Val, left.Val = left.Val, right.Val
    return head    
}

# 24. Swap Nodes in Pairs

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
    cur := head
    for cur != nil && cur.Next != nil {
        cur.Val, cur.Next.Val = cur.Next.Val, cur.Val
        cur = cur.Next.Next
    }
    return head
}

# 25. Reverse Nodes in k-Group

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
    dummy := &ListNode{Next: head}
    l, r, jump := head, head, dummy
    
    for {
        count := 0
        for r != nil && count < k {
            r = r.Next
            count += 1
        }
        if count == k {
            pre, cur := r, l
            for i := 0; i < k; i++ {
                cur.Next, cur, pre = pre, cur.Next, cur
            }
            jump.Next, jump, l = pre, l, r
        } else {
            return dummy.Next
        }
    }
}

# 21. Merge Two Sorted Lists

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    dummy := &ListNode{Next: list1}
    cur := dummy
    
    for list1 != nil && list2 != nil {
        if list1.Val < list2.Val {
            cur.Next = list1
            list1 = list1.Next
        } else {
            cur.Next = list2
            list2 = list2.Next
        }
        cur = cur.Next
    }

    if list1 != nil {
        cur.Next = list1
    }
    if list2 != nil {
        cur.Next = list2
    } 
        
    return dummy.Next
}

# 23. Merge k Sorted Lists

leetcode

Use merge two lists

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
  amount := len(lists)
  interval := 1
  for interval < amount {
    for i := 0; i < amount-interval; i += interval * 2 {
      lists[i] = mergeTwoLists(lists[i], lists[i+interval])
    }
    interval *= 2
  }

  if amount > 0 {
    return lists[0]
  }
  return nil
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
  var prehead = &ListNode{Val: -1}
  cur := prehead
  for l1 != nil && l2 != nil {
    if l1.Val <= l2.Val {
      cur.Next = l1
      l1 = l1.Next
    } else {
      cur.Next = l2
      l2 = l2.Next
    }
    cur = cur.Next
  }
  cur.Next = l2
  if l1 != nil {
    cur.Next = l1
  }

  return prehead.Next
}

# 82. Remove Duplicates from Sorted List II

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
    prev := &ListNode{Next: head}
    res := prev
    
    for prev.Next != nil {
        val := prev.Next.Val
        removed := false
        
        for prev.Next.Next != nil && prev.Next.Next.Val == val {
            prev.Next = prev.Next.Next
            removed = true
        }
        
        if removed {
            prev.Next = prev.Next.Next
            continue
        } 
        prev = prev.Next
    }
    return res.Next    
}

Share 

 Previous post: Code - Heap Next post: Code - Recursion 

© 2022 Kleon

Theme Typography by Makito

Proudly published with Hexo