更多优质内容
请关注公众号

一天一道算法题系列(2) 删除链表倒数第n个节点 、 寻找链表的中间结点 和 两个链表是否相交-张柏沛IT博客

正文内容

一天一道算法题系列(2) 删除链表倒数第n个节点 、 寻找链表的中间结点 和 两个链表是否相交

栏目:算法专题 系列: 发布时间:2022-02-23 12:01 浏览量:1170


力扣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
}

 




更多内容请关注微信公众号
zbpblog微信公众号

如果您需要转载,可以点击下方按钮可以进行复制粘贴;本站博客文章为原创,请转载时注明以下信息

张柏沛IT技术博客 > 一天一道算法题系列(2) 删除链表倒数第n个节点 、 寻找链表的中间结点 和 两个链表是否相交

热门推荐
推荐新闻