代码如下
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeNthFromEnd(head *ListNode, n int) *ListNode {
dummyhead := &ListNode { // 设置一个虚拟头结点
Next : head,
}
fast := dummyhead //并设置快慢指针
slow := fast
for i := 0 ; i <= n ; i++ { //要让慢指针走到倒数第n+1个节点，所以快指针需要先走n+1个节点。原因如下： 假设整个链表长度为size，那么快指针从虚拟头结点的位置走到nil需要size+1步，如果已经走了n+1步，则剩余的步数为size-n步。此时快慢指针同时走size-n步。此时快指针到达nil，慢指针还剩n+1步。而倒数第n个节点走到nil需要n步，那么慢指针还需要n+1步，说明慢指针此时在倒数第n+1个节点上，然后可以进行删除操作
fast = fast.Next
}
for fast != nil {
fast = fast.Next
slow = slow.Next
}
slow.Next = slow.Next.Next
return dummyhead.Next
}
链表相交
代码如下
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func getIntersectionNode(headA, headB *ListNode) *ListNode {
if headA == nil || headB == nil { //链表相交的思路如下 ，先计算两个链表的长度，并计算长 //度差，让长的链表先走长度差个位置。这是两个遍历指针 //处于统一长度的位置，这样同步向下遍历，如果相遇返回 //相遇节点，如果没相遇返回nil
return nil
}
lena := 0
lenb := 0
cura := headA
curb := headB
for cura != nil {
cura = cura.Next
lena++
}
for curb != nil {
curb = curb.Next
lenb++
}
cura = headA //遍历前需要将两个指针回到头结点再开始遍历
curb = headB
if lenb > lena {
lenc := lenb - lena
for i := 0 ; i < lenc ; i++ {
curb = curb.Next
}
}else {
lenc := lena - lenb
for i := 0 ; i < lenc ; i++ {
cura = cura.Next
}
}
for cura != nil {
if cura == curb {
return cura
}else {
cura = cura.Next
curb = curb.Next
}
}
return nil
}
142 环形链表
代码如下
思路如下 ：设置两个指针，快指针每次走两步，慢指针每次走一步。如果快慢指针相遇，说明有环。相遇的时候，在将一个头节点指针，与慢指针同步移动，如果相遇则说明该节点是环开始的节点
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func detectCycle(head *ListNode) *ListNode {
if head == nil {
return nil
}
slow := head
fast := head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
for slow != head {
slow = slow.Next
head = head.Next
}
return slow
}
}
return nil
}
