【数据结构】链表

移除链表元素

https://leetcode-cn.com/problems/remove-linked-list-elements/

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeElements(head *ListNode, val int) *ListNode {

    for head != nil && head.Val == val {
        head = head.Next
    }

    p := head

    for p != nil && p.Next != nil {
        if p.Next.Val == val {
            p.Next = p.Next.Next
        } else {
            p = p.Next
        }
    }

    return head
}

设计链表

https://leetcode-cn.com/problems/design-linked-list/

好家伙！

type MyLinkedList struct {
    Val int
    Next *MyLinkedList
}


func Constructor() MyLinkedList {
    return MyLinkedList{
        Val : 0,
        Next : nil,
    }
}

func (this *MyLinkedList) GetLen() int {
    len := 0
    for this != nil {
        len ++
        this = this.Next
    }
    return len - 1 // 去掉头节点
}


func (this *MyLinkedList) Get(index int) int {
    i := -1 // -1当作是头节点的下标
    for i != index && this != nil {
        i ++
        this = this.Next
    }
    if i == index && this != nil {
        return this.Val
    }
    return -1
}


func (this *MyLinkedList) AddAtHead(val int)  {
    head := &MyLinkedList {
        Val : val,
        Next : this.Next,
    }
    this.Next = head
}


func (this *MyLinkedList) AddAtTail(val int)  {
    tail := &MyLinkedList {
        Val : val,
        Next : nil,
    }
    for this.Next != nil {
        this = this.Next
    }
    this.Next = tail
}


func (this *MyLinkedList) AddAtIndex(index int, val int)  {
    if index < 0 {
        this.AddAtHead(val)
    } else if index == this.GetLen() {
        this.AddAtTail(val)
    } else if index < this.GetLen() {
        i := -1
        for i != index - 1 {
            i ++
            this = this.Next
        }
        tmp := &MyLinkedList {
                Val : val,
                Next : this.Next,
            }
        this.Next = tmp
    }

}


func (this *MyLinkedList) DeleteAtIndex(index int)  {
    if index >= this.GetLen() {
        return 
    }
    i := -1
    for i != index - 1 {
        i++
        this = this.Next
    }
    this.Next = this.Next.Next
}


/**
 * 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);
 */

反转链表

https://leetcode-cn.com/problems/reverse-linked-list/

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    pre := head
    current := head.Next
    pre.Next = nil
    for current != nil {
        tmp := current.Next
        current.Next = pre
        pre = current
        current = tmp
    }
    return pre
}

两两交换链表中的节点

https://leetcode-cn.com/problems/swap-nodes-in-pairs/

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {

    if head == nil || head.Next == nil {
        return head
    }

    ans := head.Next
    var pre *ListNode

    for head != nil && head.Next != nil {
        if pre != nil {
            pre.Next = head.Next
        }
        pre = head
        head = head.Next
        tmp := head.Next
        head.Next = pre
        pre.Next = tmp
        head = tmp
    }

    return ans
    
}

环形链表Ⅱ※

https://leetcode-cn.com/problems/linked-list-cycle-ii/

设置快慢指针，快指针一次走两步，慢指针一次走一步，二者相遇时一定是在环内，假设头节点到环的入口距离为$x$，入口到快慢指针相遇的位置距离为$y$，从相遇位置到环入口位置距离为$z$，如图所示。

相遇时，慢指针走过的距离为：$x+y$

快指针走过的距离为$x+y+n(z+y)$

而快指针走过的节点是慢指针的二倍，即：$2(x+y)=x+y+n(z+y)$

最终要求的是$x$，$x=(n-1)(y+z)+z$。

当$n=1$时，$x=z$，即当两指针相遇时，从相遇节点和头节点各出发一个指针，当两指针相遇时记为头口节点。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    var fast, slow *ListNode
    fast, slow = head, head

    for true {
        if fast.Next != nil && fast.Next.Next != nil {
            fast = fast.Next.Next
        } else {
            return nil
        }
        slow = slow.Next
        if fast == slow {
            index1, index2 := head, fast
            for index1 != index2 {
                index1 = index1.Next
                index2 = index2.Next
            }
            return index1
        }
    }
    return nil

}

链表相交※

https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci/

思路就是先求出两个链表的长度，求出两链表的差值，然后先让长的链表移动差值步，然后二者一块移动看指针是否相同。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    
    i, j := 0, 0

    tmp := headA
    for tmp != nil {
        tmp = tmp.Next
        i ++
    }

    tmp = headB
    for tmp != nil {
        tmp = tmp.Next
        j ++
    }

    var tmp1, tmp2 *ListNode
    var k int

    if i > j {
        tmp1 = headA
        tmp2 = headB
        k = i - j
    } else {
        tmp1 = headB
        tmp2 = headA
        k = j - i
    }

    for k > 0 {
        k-- 
        tmp1 = tmp1.Next
    }

    for tmp1 != tmp2 {
        tmp1 = tmp1.Next
        tmp2 = tmp2.Next
    }

    return tmp1

}

删除链表的倒数第N个节点※

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

双指针首先都指向头节点，快指针先走n步，然后快慢指针再一起走，直到快指针到结尾，那么慢指针下一个元素即时要删除的元素。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    nilhead := &ListNode{
        0,
        head,
    }

    fast, slow := nilhead, nilhead
    for i := 0; i <= n; i++ {
        fast = fast.Next
    }

    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }

    slow.Next = slow.Next.Next

    return nilhead.Next
}