环形链表

思路

设置快慢指针，快指针一次走两步，慢指针一次走一步，如果链表有环，则必定相遇，反之则不可以

核心代码

1
2
3
4
5
6
7
8
9

    fast:=head
    for (fast != nil && fast.Next != nil){
        head = head.Next
        fast = fast.Next.Next
        if (fast == head){
            return true
        }
    }
    return false

链表的中间节点

思路

声明一个fast，slow指针，快指针走两步，慢指针走一步，当快指针走到空时，慢指针恰好走到在中间节点。

核心代码

1
2
3
4
5
6

    fast,slow:=head,head
    for (fast != nil && fast.Next != nil){
      fast = fast.Next.Next
      slow = slow.Next
     }
    return slow

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

思路

  1. 先声明一个保护节点，保护节点指向头节点，最后直接返回保护节点的下一个节点，即头节点。
  2. 1=>2=>3=>4=>5
  3. 如果要删除倒数第2个节点(4),其实我们只需要找到倒数第3个节点即(3)，即找到倒数第N+1个节点。
  4. 如果快指针走到尽头，慢指针刚好到倒数第n+1个节点，我们就可以运用快慢指针的思想。
  5. 关键问题
    1. 快慢指针补发是否需要保持一致？
    2. 快指针需要领先慢指针多少步？
      1. 慢指针走L-(n+1)步
      2. 快指针需要提前走L-[L-(n+1)]=n+1步

核心代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

    p:=&Listnode{val:0 Next:head}
    fast,slow:=head,p
    for i:=0 ;i < n ;i++{
        fast = fast.Next
    }
    for fast!=nil{
        fast = fast.Next
        slow = slow.Next
    }
    slow = slow.Next.Next
    return p.Next

合并两个有序链表

思路

过滤器+双指针+保护节点

  1. 一直遍历2个链表直到为空
  2. 当链表2为空或者链表1不为空且链表1的值小于链表2时

核心代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

    head:=&ListNode{Val:0,Next:nil}
    p:=head
    for (list1!=nil || list2!=nil ){
        if (list2 == nil || (list1!=nil &&list1.Val<list2.Val)){
            head.Next = list1
            list1 = list1.Next
        }else{
            head.Next = list2
            list2 = list2.Next
        }
        head = head.Next
    }
    return p.Next

反转链表

思路

1=>2=>3=>4=>5=>nil

nil<=1 2

  1. 让1与2的关系断裂之前，需要先将2的节点进行保存 next:=cur.Next

核心代码

1
2
3
4
5
6
7
8

    var help *ListNode
    for cur!=nil{
        next:=cur.Next
        cur.Next =help
        help = cur 
        cur = cur.Next
}
return help

K个一组反转链表

1=>2=>3=>4=>5

思路

  1. 分组,往后遍历k-1步，为一组，head&end
  2. 组内做反转(反转链表的题解)
  3. 维护组间的边，前一个租、后一个组的边

核心代码

回文链表

思路

  1. 将链表中的值存放进数组中
  2. 进而用双指针进行判断

核心代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

    arrays:=[]int{}
    for head!=nil{
        arrays:=append(arrays,head.Val)
        head = head.Next
    }
    start,end:=0,len(arrays)-1
    for start < end{
        if vals[start]!=vals[end]{
        return false
        }
        start++
        end--
    }
    return true