List feature

1. Definition of singly linked lists

Single-linked lists are typically defined as follows:

type ListNode struct {
	Val  int
	Next *ListNode
}
Copy the code

2. Basic operations of singly linked lists

1. Insert the

Add a new value after the given node prev:

Initialize the new nodecur

willcur 的 nextField links toprevThe next field ofnext

willprev 的 nextField links tocur

The insertion time is O(1), but it needs to be traversed firstprev, so the worst time complexity is O(n).

Intermediate node insertion

func add(prev *ListNode, val int) {
    1. Initialize cur
    cur := &ListNode{Val: val}
    // 2. Cur next points to Prev next
    cur.Next = prev.Next
    // 3. Prev next points to cur
    prev.Next = cur
}
Copy the code

His head

func addHead(head *ListNode, val int) *ListNode {
    1. Initialize cur
    cur := &ListNode{Val: val}
    // 2. Cur next points to head
    cur.Next = head
    // 3. Cur is the new head
    head = cur
    // 4. Return head
    return head
}
Copy the code

2. Delete the

Delete existing node cur:

findcurThe last node ofprevAnd the next nodenext

willprev 的 nextPoint to thenextnode

The time complexity of deletion is O(1), but it must be traversed to find itprevNode, so the time is order n.

Delete intermediate nodes

func delete(prev *ListNode) {
    // 1. Find the node cur to be deleted
	cur := prev.Next
    // 2. Prev next points to cur next
	prev.Next = cur.Next
    // 3. Clear the pointer to cur
	cur.Next = nil
}
Copy the code

The first delete

func deleteHead(head *ListNode) *ListNode {
    // 1. Get new head
    newHead := head.Next
    // 2. The original head points to nil
    head.Next = nil
    // 3. Return the new head
    return newHead
}
Copy the code

3. The traverse

func traversal(head *ListNode) {
	forhead ! =nil {
		head = head.Next
	}
}
Copy the code

3. Precautions

Consider the prev of the operation node. Since insertion or deletion requires a preV, consider how to obtain this node
Note that the node is always checked for null before calling the Next field
Note the end condition, boundary value condition
A general test case for a linked list, typically an odd or even number of nodes or a single node

4

1. Fast and slow pointer

Define two Pointers, one is fast (first or a few steps at a time), the other is slow (a step at a time), can solve such as links in the list, the intersection of the list, find the list of the reciprocal items and other problems

1. Looking for a ring

Fast and slow hands go together, can bump together means there is a ring

// Notice how fast starts as head
fast, slow := head, head
forfast ! = slow { fast = fast.Next.Next slow = slow.Next.Next }Copy the code

2. Find the intermediate node

To find the middle node is mainly to split the linked list into two sections, after the operation, using the fast and slow pointer to find the middle node, and usually is a little more in front

// Notice that fast starts with head.Next, so you need to make sure that head exists.
// Do this without considering the parity of the number of nodes
fast, slow := head.Next, head
forfast ! =nil&& fast.Next ! =nil {
    fast = fast.Next.Next
    slow = slow.Next
}
// At this point, slow is the prev for the second half of the list
// 1->2->3->4->5
/ / 1 - > 2 - > 3 - > 4 - > 5 - > 6 fast jump step 2, missile to 3, 4 - > rHead = 5 - > 6
rHead := slow.Next
// Break the link between the front and back lists
slow.Next = nil
Copy the code

2. Virtual head node

When the head node needs to be specially identified, we can add a virtual head node in front of the head node to make the original head node become the intermediate node, so as to unify the insertion and deletion operations

1. Insert the

func add(head *ListNode, val int) *ListNode {
    dummy := &ListNode{Next: head}
    // Or by some other means, get the previous node to insert the node
    prev := dummy
    / / head
    cur := &ListNode{Val: val}
    cur.Next = prev.Next
    prev.Next = cur
    return dummy.Next
}
Copy the code

2. Delete the

func delete(head *ListNode) *ListNode {
    dummy := &ListNode{Next: head}
    // Or by some other means, get the previous node to insert the node
    prev := dummy
    / / delete
    cur := prev.Next
    prev.Next = cur.Next
    cur.Next = nil
    return dummy.Next
}

Copy the code

3. Flip the list

Flipping a linked list usually requires splitting the list into three parts: the part before flipping, the flipped list, and the rest of the flipped listAdd a, B, c, d to the breakpoint and you want it to look like this:B, C are the heads and tails of the parts to be flipped; A and D are the precursor and successor of the part of the linked list that needs to be flipped. The whole flipping process is as follows:

Find a, B, C, d
Let’s cut the connection between C and D
Send with B as head to flip
A points to C, b points to D

exercises

707. Design linked lists

type MyLinkedList struct {
    Val int
    Next *MyLinkedList
    // Define the length of the list
    len int
}

func Constructor(a) MyLinkedList {
    return MyLinkedList{}
}

func (this *MyLinkedList) Get(index int) int {
    if this.len < index+1 {
        return - 1
    }
    cur := this.Next
    for i := 0; i < index; i++ {
        cur = cur.Next
    }
    return cur.Val
}

func (this *MyLinkedList) AddAtHead(val int)  {
    cur := &MyLinkedList{Val: val}
    cur.Next = this.Next
    this.Next = cur
    this.len++
}

func (this *MyLinkedList) AddAtTail(val int)  {
    if this.len= =0 {
        this.AddAtHead(val)
    } else {
        prev := this
        forprev.Next ! =nil {
            prev = prev.Next
        }
        cur := &MyLinkedList{Val: val}
        prev.Next = cur
        this.len+ +}}func (this *MyLinkedList) AddAtIndex(index int, val int)  {
    if index == this.len { 
        this.AddAtTail(val)
    } else if index <= 0 {
        this.AddAtHead(val)
    } else if index < this.len {
        prev := this
        for i := 0; i < index; i++ {
            prev = prev.Next
        }
        cur := &MyLinkedList{Val: val}
        cur.Next = prev.Next
        prev.Next = cur
        this.len+ +}}func (this *MyLinkedList) DeleteAtIndex(index int)  {
    if index < this.len && index >= 0 {
        prev := this
        for i := 0; i < index; i++ {
            prev = prev.Next
        }
        cur := prev.Next
        prev.Next = cur.Next
        cur.Next = nil
        this.len-}}/** * Your MyLinkedList object will be instantiated and called as such: * obj := Constructor(); * param_1 := obj.Get(index); * obj.AddAtHead(val); * obj.AddAtTail(val); * obj.AddAtIndex(index,val); * obj.DeleteAtIndex(index); * /
Copy the code

141. Circular linked lists

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */
// The speed pointer
func hasCycle(head *ListNode) bool {
    fast, slow := head, head
    forfast ! =nil&& fast.Next ! =nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            return true}}return false
}
Copy the code

142. Circular linked List II

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */
// Start a new node from the ring and head
func detectCycle(head *ListNode) *ListNode {
    fast, slow := head, head
    forfast ! =nil&& fast.Next ! =nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            cur := head
            forcur ! = slow { cur = cur.Next slow = slow.Next }return cur
        }
    }
    return nil
}
Copy the code

160. Intersecting linked lists

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */
// a traverses from a to B
// b traverses from b to A
// An encounter is an intersection
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    a, b := headA, headB
    fora ! = b {if a == nil {
            a = headB
        } else {
            a = a.Next
        }
        if b == nil {
            b = headA
        } else {
            b = b.Next
        }
    }
    return a
}
Copy the code

22. The k last node in the linked list

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */
// The speed pointer
// The fast pointer takes k steps first, and the slow pointer takes k steps together
func getKthFromEnd(head *ListNode, k int) *ListNode {
    fast := head
    for i := 0; i < k; i++ {
        fast = fast.Next
    }
    slow := head
    forfast ! =nil {
        fast = fast.Next
        slow = slow.Next
    }
    return slow
}
Copy the code

Delete the NTH node from the list

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */
// Virtual head node + fast/slow pointer
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Next: head}
    fast := head
    for i := 0; i < n; i++ {
        fast = fast.Next
    }
    prev := dummy
    forfast ! =nil {
        fast = fast.Next
        prev = prev.Next
    }
    prev.Next = prev.Next.Next
    return dummy.Next
}
Copy the code

21. Merge two ordered lists

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */
// Part of merge sort
// Virtual head node + double pointer
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    dummy := &ListNode{}
    cur := dummy
    forl1 ! =nil&& l2 ! =nil {
        if l1.Val < l2.Val {
            cur.Next = l1
            l1 = l1.Next
        } else {
            cur.Next = l2
            l2 = l2.Next
        }
        cur = cur.Next
    }
    ifl1 ! =nil {
        cur.Next = l1
    }
    ifl2 ! =nil {
        cur.Next = l2
    }
    return dummy.Next
}
Copy the code

83. Delete duplicate elements from sorted linked lists

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */
func deleteDuplicates(head *ListNode) *ListNode {
    cur := head 
    forcur ! =nil&& cur.Next ! =nil {
        if cur.Val == cur.Next.Val {
            cur.Next = cur.Next.Next
        } else {
            cur = cur.Next
        }
    }
    return head
}
Copy the code

Delete duplicate element II from sorted list

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */
func deleteDuplicates(head *ListNode) *ListNode {
    dummy := &ListNode{Next: head, Val: - 999.}
    prev := dummy
    forhead ! =nil&& head.Next ! =nil {
        // There is a repetition
        if head.Val == head.Next.Val {
            next := head.Next
            // Multiple duplicate values are possible
            fornext ! =nil && next.Val == head.Val {
                next = next.Next
            }
            prev.Next = next
            head = prev.Next
        } else {
            prev = head
            head = head.Next
        }
    }
    return dummy.Next
}
Copy the code

206. Reverse linked lists

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */
func reverseList(head *ListNode) *ListNode {
    var newHead *ListNode
    forhead ! =nil {
        next := head.Next
        head.Next = newHead
        newHead = head
        head = next
    }
    return newHead
}
Copy the code

203. Remove linked list elements

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */
// Virtual head node
func removeElements(head *ListNode, val int) *ListNode {
    dummy := &ListNode{Next: head}
    prev := dummy
    forhead ! =nil {
        if head.Val == val {
            prev.Next = prev.Next.Next
        } else {
            prev = head
        }
        head = head.Next
    }
    return dummy.Next
}
Copy the code

234. Palindrome linked list

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */
/ / double pointer
// The fast pointer takes two steps and the slow pointer takes one step
// When the fast pointer finishes, the slow pointer moves to the middle and reverses the last part of the list
// Compare the first half of the list with the second half after the reversal
func isPalindrome(head *ListNode) bool {
    fast, slow := head.Next, head
    forfast ! =nil&& fast.Next ! =nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    right := reverseList(slow.Next)
    left := head
    forright ! =nil {
        ifleft.Val ! = right.Val {return false
        }
        left = left.Next
        right = right.Next
    }
    return true
}
func reverseList(head *ListNode) *ListNode {
    var newHead *ListNode
    forhead ! =nil {
        next := head.Next
        head.Next = newHead
        newHead = head
        head = next
    }
    return newHead
}
Copy the code

2. Add two numbers

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    c := 0
    dummy := &ListNode{}
    prev := dummy
    forl1 ! =nil|| l2 ! =nil || c == 1 {
        count := c
        ifl1 ! =nil {
            count += l1.Val
            l1 = l1.Next
        }
        ifl2 ! =nil {
            count += l2.Val
            l2 = l2.Next
        }
        c = count/10
        count = count%10
        prev.Next = &ListNode{Val: count}
        prev = prev.Next
    }
    return dummy.Next
}
Copy the code

61. Rotate linked lists

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */
// Fast and slow pointer + virtual head node
// The fast pointer moves k%len first, and the slow pointer moves again
func rotateRight(head *ListNode, k int) *ListNode {
    len: =0
    cur := head
    forcur ! =nil {
        cur = cur.Next
        len++
    }
    if len< =1 {
        return head
    }
    k = k % len
    if k == 0 {
        return head
    }
    fast := head
    for i := 0; i < k; i++ {
        fast = fast.Next
    }
    prev := head
    // Run one step less to handle node relationships
    forfast.Next ! =nil {
        fast = fast.Next
        prev = prev.Next
    }
    next := prev.Next
    prev.Next = nil
    fast.Next = head
    head = next
    return head
}
Copy the code

86. Separate linked lists

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */
// Virtual head node
// less than a string
// Greater than or equal to a string
// The last small string is greater than or equal to
func partition(head *ListNode, x int) *ListNode {
    ltHead := &ListNode{}
    geHead := &ListNode{}
    small, big := ltHead, geHead
    forhead ! =nil {
        v := head.Val
        if v < x {
            small.Next = &ListNode{Val: v}
            small = small.Next
        } else {
            big.Next = &ListNode{Val: v}
            big = big.Next
        }
        head = head.Next
    }
    small.Next = geHead.Next
    return ltHead.Next
}
Copy the code

92. Reverse linked list II

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */
// Remove it, turn it over and put it back
func reverseBetween(head *ListNode, left int, right int) *ListNode {
    if left == right {
        return head
    }
    dummy := &ListNode{Next: head}
    prev := dummy
    // To the front left
    for i := 0; i < left- 1; i++ {
        prev = prev.Next
    }
    reverseHead := prev.Next
    reversePre := prev
    for i := 0; i < right-left+1; i++ {
        prev = prev.Next
    }
    // Preserve the sequential node
    next := prev.Next
    // Remove the list to be flipped
    prev.Next = nil
    newHead := reverseList(reverseHead)
    // reconnect the new head
    reversePre.Next = newHead
    // The previous header is reversed to become the last one
    reverseHead.Next = next
    return dummy.Next
}
func reverseList(head *ListNode) *ListNode {
    var newHead *ListNode
    forhead ! =nil {
        next := head.Next
        head.Next = newHead
        newHead = head
        head = next
    }
    return newHead
}
Copy the code

138. Copy linked lists with random Pointers

/** * Definition for a Node. * type Node struct { * Val int * Next *Node * Random *Node * } */
// Create the original node: map the new node
func copyRandomList(head *Node) *Node {
    m := make(map[*Node]*Node)
    cur := head
    forcur ! =nil {
        m[cur] = &Node{Val: cur.Val}
        cur = cur.Next
    }
    cur = head
    forcur ! =nil {
        m[cur].Next = m[cur.Next]
        m[cur].Random = m[cur.Random]
        cur = cur.Next
    }
    return m[head]
}
Copy the code

143. Rearrange linked lists

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */
/ * 1 - > 2 - > 3 - > 4 - > 5 as article number back to split into two linked list, retain more in front of the 1 - > 2 - > 3 4 - > 5 flip a list after 1 - > 2 - > 3, 5 - > 4 are arranged in a row - > 5 - > 4 - > 2 - > 3 * /
func reorderList(head *ListNode)  {
    // Split the list into two
    fast, slow := head, head
    forfast ! =nil&& fast.Next ! =nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    rehead := slow.Next
    // Break the first and second lists
    slow.Next = nil
    // The next list is flipped
    newHead := reverseList(rehead)
    // merge two lists
    cur := head
    curNew := newHead
    forcur ! =nil&& curNew ! =nil {
        newNext := curNew.Next
        curNew.Next = cur.Next
        cur.Next = curNew
        curNew = newNext
        cur = cur.Next.Next
    }
}
func reverseList(head *ListNode) *ListNode {
    var newHead *ListNode
    forhead ! =nil {
        next := head.Next
        head.Next = newHead
        newHead = head
        head = next
    }
    return newHead
}
Copy the code

148. Sort linked lists

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */
// merge sort, use the fast pointer to find the middle node, split the list into two segments
func sortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    fast, slow := head.Next, head
    forfast ! =nil&& fast.Next ! =nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    rHead := slow.Next
    slow.Next = nil
    left := sortList(head)
    right := sortList(rHead)
    return merge(left, right)
}
func merge(l *ListNode, r *ListNode) *ListNode {
    dummy := &ListNode{}
    prev := dummy
    forl ! =nil&& r ! =nil {
        if l.Val < r.Val {
            prev.Next = l
            l = l.Next
        } else {
            prev.Next = r
            r = r.Next
        }
        prev = prev.Next
    }
    ifl ! =nil {
        prev.Next = l
    }
    ifr ! =nil {
        prev.Next = r
    }
    return dummy.Next
}
Copy the code

1. Definition of singly linked lists

2. Basic operations of singly linked lists

1. Insert the

Intermediate node insertion

His head

2. Delete the

Delete intermediate nodes

The first delete

3. The traverse

3. Precautions

4

1. Fast and slow pointer

1. Looking for a ring

2. Find the intermediate node

2. Virtual head node

1. Insert the

2. Delete the

3. Flip the list

exercises

707. Design linked lists

141. Circular linked lists

142. Circular linked List II

160. Intersecting linked lists

22. The k last node in the linked list

Delete the NTH node from the list

21. Merge two ordered lists

83. Delete duplicate elements from sorted linked lists

Delete duplicate element II from sorted list

206. Reverse linked lists

203. Remove linked list elements

234. Palindrome linked list

2. Add two numbers

61. Rotate linked lists

86. Separate linked lists

92. Reverse linked list II

138. Copy linked lists with random Pointers

143. Rearrange linked lists

148. Sort linked lists

Related Posts

Summing only does not have a summation method for BigDecimal

Timestamps for BigQuery. Syntax and example query simplification 101

After reading this article, stop saying that you have learned MySQL.