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

一天一道算法题系列(3) 翻转链表、按区间翻转链表、k个一组翻转链表-张柏沛IT博客

正文内容

一天一道算法题系列(3) 翻转链表、按区间翻转链表、k个一组翻转链表

栏目:算法专题 系列: 发布时间:2022-02-24 23:47 浏览量:179

力扣T206:给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

分析:这是一道比较简单的题目,但是了解它的思想比做这道题本身更重要。

可以分为递归和迭代两种做法。迭代法比较常规而且节省内存,但使用对这道题递归可以让我们学会递归的思维模式。

迭代法思路需要用到p1/p2/p3共3个指针。

func reverseList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil{
		return head
	}
	p1, p2 := head, head.Next
	for p2 != nil{
		p3 := p2.Next
		p2.Next = p1
		p1 = p2
		p2 = p3
	}
	head.Next = nil
	return p1
}

 

假设有A->B->C->D->E五个节点,反转函数为reverseList。递归思路就是:reverseList(A~E)等价于A.Next=nil再把reverseList(B~E)的最后一个节点指向A:

func reverseList0(head *ListNode) *ListNode {
	if head == nil || head.Next== nil{
		return head
	}

	newHead := reverseList0(head.Next)
	head.Next.Next = head
	head.Next = nil
	return newHead
}

 

 

力扣T92: 给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。

分析:只需要先用一个指针遍历到left节点之后,再让p1和p2分别指向left和left.next往后遍历并交换(和上一题一样的行为),直到边界right为止。

func reverseBetween(head *ListNode, left int, right int) *ListNode {
	if left == right{
		return head
	}

	dummy := &ListNode{}
	dummy.Next = head
	p1 := dummy
	for i:=0; i<left-1; i++{
		p1 = p1.Next
	}
	conn1 := p1
	p1 = p1.Next
	p2 := p1.Next
	p3 := p2
	for i := 1; i<=right-left; i++{
		p3=p2.Next
		p2.Next = p1
		p1 = p2
		p2 = p3
	}

	conn1.Next.Next = p3
	conn1.Next = p1
	return dummy.Next
}

 

 

力扣T25:K 个一组翻转链表

给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

已给出函数签名:

func ReverseKGroup(head *ListNode, k int) *ListNode

 

按递归的思想,ReverseKGroup(head, k)就相当于把前k个节点逆转之后再对第k+1个节点调用ReverseKGroup(headK, k)。

func reverseKGroup(head *ListNode, k int) *ListNode {
	if head == nil{
		return nil
	}
	newHead, tail, nextGroup, succ := reverseKNode(head, k)
	if !succ{
		reverseKNode(newHead, k)
		return tail
	}
	if nextGroup == nil{
		return newHead
	}
	tail.Next = reverseKGroup(nextGroup, k)
	return newHead
}

func reverseKNode(head *ListNode, k int) (*ListNode, *ListNode, *ListNode, bool){
	t := k-1
	if head == nil || head.Next == nil{
		return head,head,nil, true
	}
	p1, p2 := head, head.Next
	for i:=1; i<k; i++{
		if p2 == nil{
			break
		}
		p3 := p2.Next
		p2.Next = p1
		p1 = p2
		p2 = p3
		t--
	}
	head.Next = nil
	return p1, head, p2, t == 0
}

 

 

力扣T234:给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。

要求用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题。

分析:用快慢指针找到中间节点,再反转中间节点后的那一半节点,然后就可以在用新的双指针从链表两端往中间遍历比对:

func reverseList(head *ListNode) *ListNode {
    var prev, cur *ListNode = nil, head
    for cur != nil {
        nextTmp := cur.Next
        cur.Next = prev
        prev = cur
        cur = nextTmp
    }
    return prev
}

func endOfFirstHalf(head *ListNode) *ListNode {
    fast := head
    slow := head
    for fast.Next != nil && fast.Next.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    return slow
}

func isPalindrome(head *ListNode) bool {
    if head == nil {
        return true
    }

    // 找到前半部分链表的尾节点并反转后半部分链表
    firstHalfEnd := endOfFirstHalf(head)
    secondHalfStart := reverseList(firstHalfEnd.Next)

    // 判断是否回文
    p1 := head
    p2 := secondHalfStart
    result := true
    for result && p2 != nil {
        if p1.Val != p2.Val {
            result = false
        }
        p1 = p1.Next
        p2 = p2.Next
    }

    // 还原链表并返回结果
    firstHalfEnd.Next = reverseList(secondHalfStart)
    return result
}

 

 

下面是递归法,时间复杂度和空间复杂度都是O(n):

func isPalindrome(head *ListNode) bool {
	p1,  res := head, true
	var iterList func (h *ListNode)
	iterList = func(h *ListNode){
		if h == nil{
			return
		}
		iterList(h)
		if h != p1{
			res = false
			return
		}
	}
	return res
}

 




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

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

张柏沛IT技术博客 > 一天一道算法题系列(3) 翻转链表、按区间翻转链表、k个一组翻转链表

热门推荐
推荐新闻