​
力扣T19

给你一个链表，删除链表的倒数第 k 个结点，并且返回链表的头结点。

分析：

本题其实是要找到倒数第k+1个节点node，并将该节点的next指向倒数第k-1个节点。

2种中规中矩的方法是：

1、遍历2次链表，第一次遍历可以得知长度n，倒数第k个节点就是正数第n-k+1个节点，遍历第二次即可得到该节点；时间复杂度O(n)，空间复杂度O(1)

2、遍历1次链表，将所有节点指针记录到一个hashmap中，以节点的序号（从1开始）作为key，节点指针作为value，然后直接从hashmap取key为n-k+1的节点；时间和空间复杂度为O(n)，但是比方法A少遍历1次。

有没有只遍历一次且空间复杂度为O(1)的方法？

 

其实单链表的解题套路无非就是双指针法，只不过双指针有各种玩法如同时出发，不同时出发，快慢指针等。

本题我们先用一个指针p1从头结点出发，让其走到第k个节点时，创建第二个指针p2指向头结点并一起跟着第一个指针往后走。当p1走到最后一个节点n时，p2就走到n-k+1个节点处，即倒数第k个节点。

代码实现：

func removeNthFromEnd(head *ListNode, k int) *ListNode{
    dummy := &ListNode{Val:-1, Next: head}        // 使用虚拟头结点可以轻松解决当n=k的情况下要处理空指针的问题，因为此时倒数第k+1个节点nodeKPrev是nil
    nodeKPrev := GetLastKNode(dummy, k+1)
    nodeK := nodeKPrev.Next
    if nodeKPrev == nil || nodeK == nil{    // 为nil表示k超出了链表范围即 k<1或 k>n
        return head
    }

    nodeKPrev.Next = nodeKPrev.Next.Next
    nodeK.Next = nil    // 这行可有可无
    return dummy.Next
}

 

另一个只遍历1次的思路是使用后序遍历，这是一种递归的思想：removeNthFromEnd(head)表示删除链表的倒数第n个节点。先head的倒数第n个节点，相当于删除head.N的倒数第n个节点，如果head的倒数第k+1个节点就是head，就执行删除，如果不是则什么都不做。

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{}
    dummy.Next = head
    k := 0
    var removeNthFromEndHelper  func (h *ListNode, n int)
    removeNthFromEndHelper = func (h *ListNode, n int){
        if h.Next == nil{
            k = 1
            return
        }

        removeNthFromEndHelper(h.Next, n)
        k++
        if n+1 == k{
            p := h.Next
            h.Next = h.Next.Next
            p.Next = nil
            return
        }
    }
    removeNthFromEndHelper(dummy, n)
    return dummy.Next
}

 

 

力扣T876: 给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

分析：使用双指针+快慢指针。快指针走两步，慢指针走一步，快指针走完的时候慢指针就走到中间节点。

func middleNode(head *ListNode) *ListNode {
    dummy := &ListNode{}
    dummy.Next = head
    p1, p2 := dummy, dummy
    isOdd := false

    for ;p2 != nil;isOdd=true{
        p2 = p2.Next
        if p2 == nil{
            isOdd = false
            break
        }
        p2 = p2.Next
        p1 = p1.Next
    }

    if isOdd{
        return p1
    }
    return p1.Next
}

​

两个链表是否相交

力扣T160: 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

分析：这道题如果使用双层循环可以简单的解决。但如果要达到O(n)的复杂度则需要一些技巧。

我们使用双指针p1和p2，从A和B头结点出发，p1和p2同时前进。假设A和B的相交节点都是他们自身的第k个节点那么双指针可以相遇，但这里可能他们的相交节点分别是自身的第k1和k2个节点。

解决方法是将A和B两条链表拼起来，让p1从A开始走，如果走完A再从B开始走；而p2从B开始走，走完B再走A。如果A和B相交，则p1和p2一定会走到同一个节点，此时停止循环，返回重合节点。

如果A和B没有相交节点我们可以把nil作为他们的虚拟相交节点，也就是说，即使AB没有相交节点，p1和p2也会重合(即p1 == p2)，不过此时p1和p2都是nil。

如图：

 

func getIntersectionNode(headA, headB *ListNode) *ListNode{		
	if headA == nil || headB == nil{
		return nil
	}

	if headA == headB{	// 第一个节点就是相交节点的情况（按理说这种情况不合理，因为如果第一个节点是相交节点，那么这个节点就会有两个不同的Next指针了。但是力扣要求校验这种情况）
		return headA
	}

	p1 := headA
	p2 := headB
	p1FinishA := false		// p1是否走完链表A
	//p2FinishB := false

	for !p1FinishA || p1.Next != nil{	// 当p1走完链表A再走完链表B则跳出循环，此时p2也同时走完了A+B，所以for只需判断p1即可
		p1 = p1.Next
		if p1 == nil{
			p1 = headB
			p1FinishA = true
		}

		p2 = p2.Next
		if p2 == nil{
			p2 = headA
			//p2FinishB = true
		}

		if p1 == p2{
			return p1
		}
	}

	return nil
}