linkedlist

func BuildLinkedList ¶

func BuildLinkedList(values []int) *ListNode

BuildLinkedList 没有头节点的单链表

func BuildLinkedList2 ¶

func BuildLinkedList2(nums []int) *ListNode

func DeleteLinkedList ¶

func DeleteLinkedList(head *ListNode, position int) (*ListNode, error)

DeleteLinkedList 下标从0开始

func DetectCycle ¶

func DetectCycle(head *ListNode) *ListNode

DetectCycle map存储节点，有环会再次遇到

func DetectCycle2 ¶

func DetectCycle2(head *ListNode) *ListNode

DetectCycle2 快慢指针 我们使用两个指针，fast 与 slow。它们起始都位于链表的头部。随后，slow 指针每次向后移动一个位置， 而 fast 指针向后移动两个位置。如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇。 当发现 slow 与 fast 相遇时，我们再额外使用一个指针 ptr 。起始，它指向链表头部；随后，它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇

func GetIntersectionNode ¶

func GetIntersectionNode(headA, headB *ListNode) *ListNode

GetIntersectionNode 两个链表直接比较，时间复杂度 O(N^2)

func GetIntersectionNode2 ¶

func GetIntersectionNode2(headA, headB *ListNode) *ListNode

GetIntersectionNode2 记录下来链表每个节点比较

func InsertLinkedList ¶

func InsertLinkedList(head *ListNode, value, position int) (*ListNode, error)

InsertLinkedList 头插法，下标从0开始

func MergeTwoLists ¶

func MergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode

MergeTwoLists 递归 将两个链表里面值小的和另一个链表合并

func MergeTwoLists2 ¶

func MergeTwoLists2(list1 *ListNode, list2 *ListNode) *ListNode

MergeTwoLists2 新建一个链表，将两个链表合并过来

func RemoveNthFromEnd ¶

func RemoveNthFromEnd(head *ListNode, n int) *ListNode

func RemoveNthFromEnd2 ¶

func RemoveNthFromEnd2(head *ListNode, n int) *ListNode

RemoveNthFromEnd2 我们也可以在遍历链表的同时将所有节点依次入栈。根据栈「先进后出」的原则， 我们弹出栈的第 n 个节点就是需要删除的节点， 并且目前栈顶的节点就是待删除节点的前驱节点。 这样一来，删除操作就变得十分方便了

func RemoveNthFromEnd3 ¶

func RemoveNthFromEnd3(head *ListNode, n int) *ListNode

RemoveNthFromEnd3 遍历一遍存储每个节点，然后再删掉第 len(nodes) - n 个节点

func RemoveNthFromEnd4 ¶

func RemoveNthFromEnd4(head *ListNode, n int) *ListNode

RemoveNthFromEnd4 双指针，first 先走n步，然后second再走， 当first到尾部时，second位置的下一个就是待删除节点 时间复杂度: O(L), L 是链表长度 空间复杂度: O(1)

func RemoveNthFromEnd5 ¶

func RemoveNthFromEnd5(head *ListNode, n int) *ListNode

func ReverseList ¶

func ReverseList(head *ListNode) *ListNode

ReverseList 迭代法: 记录前一个节点和后一个节点，遍历时候改为向前的指针，时间复杂度O(N)

func ReverseList2 ¶

func ReverseList2(head *ListNode) *ListNode

ReverseList2 递归法

func ReverseList3 ¶

func ReverseList3(head *ListNode) *ListNode

ReverseList3 头插法插入新链表

func ReverseList4 ¶

func ReverseList4(head *ListNode) *ListNode

ReverseList4 遍历一遍节点存下来，重建链表

func ReverseList5 ¶

func ReverseList5(head *ListNode) *ListNode