首页 > 其他分享 >Leetcode刷题day4-链表.交换.删除.相交.环

Leetcode刷题day4-链表.交换.删除.相交.环

时间:2023-12-02 22:44:06浏览次数:29  
标签:head day4 fast self 链表 node1 next Leetcode

24.两两交换链表中的节点

24. 两两交换链表中的节点 - 力扣(LeetCode)
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(只能进行节点交换)。

  • 示例 1:
    • 输入:head = [1,2,3,4]
    • 输出:[2,1,4,3]
  • 示例 2:
    • 输入:head = []
    • 输出:[]
  • 示例 3:
    • 输入:head = [1]
    • 输出:[1]
      解题思路
    1. 虚拟头:node0、node1=head、node2=head.next、node3=head.next.next
      node0->node2, node2->node1, node1->node3; node0=node1, node1=node3
    2. 递归法:node1=head, node2=head.next, node3=head.next.next
      交换node2.next=node1, 递归node1.next=self.swap(node3)
class ListNode():
	def __init__(self,val=0,next=None):
		self.val=val
		self.next=next

class Solution():
	def swapPairs(head):  # 迭代法
		dummy_head = ListNode(next=head)
		node0 = dummy_head
		node1 = head
		while node1 and node1.next:
			node2 = node1.next
			node3 = node2.next
			# 交换
			node0.next = node2
			node2.next = node1
			node1.next = node3

			node0 = node1
			node1 = node3
		return dummy_head.next

	def swapPairs(head):  # 递归法
		if head is None or head.next is None:
			return head
		node1 = head
		node2 = head.next
		node3 = head.next.next

		node2.next = node1
		node1.next = self.swapPairs(node3)

		return node2

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

19. 删除链表的倒数第 N 个结点 - 力扣(LeetCode)
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

  • 示例 1:

    • 输入:head = [1,2,3,4,5], n = 2
    • 输出:[1,2,3,5]
  • 示例 2:

    • 输入:head = [1], n = 1
    • 输出:[]
  • 示例 3:

    • 输入:head = [1,2], n = 1
    • 输出:[1]
      解题思路
    1. 暴力求解:反转链表 -> 删除第n-1个节点 -> 反转链表
    2. 双指针:双指针先指向虚拟头节点, 快指针先走n+1步, 双指针同时走, 直到快指针为None, 慢指针.next->慢指针.next.next
class ListNode():
	def __init__(val=0,next=None):
		self.val=val
		self.next=next

class Solution():
	def removeNthFromEnd(self,head,n):  # 暴力求解法
		reverse_head = self.reverse1(head)
		current = dummy_head = ListNode(next=reverse_head)
		for _ in range(n-1):
			current = current.next
		current.next = current.next.next
		final_head = self.reverse1(dummy_head.next)
		return final_head

	def reverse1(self,head):  # 反转链表方法1
		if head is None or head.next is None:
			return head
		new_head = self.reverse(head.next)
		head.next.next = head
		head.next = None
		return new_head

	def reverse2(self,head):  # 反转链表方法2
		pre = None
		cur = head
		while cur:
			cur.next,pre,cur = pre,cur,cur.next
		return pre

	def removeNthFromEnd(self,head,n):
		if head is None:
			return
		fast = slow = dummy_head = ListNode(next=head)
		for _ in range(n+1):
			fast=fast.next
		while fast:
			slow=slow.next
			fast=fast.next
		slow.next=slow.next.next
		return dummy_head.next

面试题.链表相交

面试题 02.07. 链表相交 - 力扣(LeetCode)
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。

  • 图示两个链表在节点 c1 开始相交
  • 题目数据 保证 整个链式结构中不存在环。
  • 注意,函数返回结果后,链表必须 保持其原始结构 。
    解题思路:
    若两链表相交,则最后某段必然相同,从短链表起点处开始遍历两链表,必然有相同节点
class ListNode():
	def __init__(self,val=val,next=next):
		self.val=val
		self.next=next

class Solution():
	def getIntersectionNode(self,headA,headB):
		copyA,copyB,lenA,lenB = headA,headB,0,0
		while copyA:
			copyA=copyA.next
			lenA+=1
		while copyB:
			copyB=copyB.next
			lenB+=1
		if lenA<lenB:
			lenA,lenB = lenB,lenA
			headA,headB = headB,headA
		for _ in range(lenA-lenB):
			headA=headA.next
		while headA and headB:
			if headA==headB:
				return headA
			headA=headA.next
			headB=headB.next
		return None

142.环形链表Ⅱ

142. 环形链表 II - 力扣(LeetCode)
给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。不允许修改 链表。

  • 示例 1:
    • 输入:head = [3,2,0,-4], pos = 1
    • 输出:返回索引为 1 的链表节点
    • 解释:链表中有一个环,其尾部连接到第二个节点。

解题思路:
双指针:若有环,①快指针两步,慢指针一步,直到指针相交;②快指针初始化至head,快慢指针依次遍历,直到相交,交点即为入环点。

class ListNode():
	def __init__(self,val=val,next=next):
		self.val=val
		self.next=next
classSolution():
	def detectCycle(self,head):
		fast,slow=head,head
        while fast and fast.next:
            fast=fast.next.next
            slow=slow.next
            if fast==slow:
                fast=head
                while fast!=slow:
                    fast=fast.next
                    slow=slow.next
                return fast
        return None

标签:head,day4,fast,self,链表,node1,next,Leetcode
From: https://www.cnblogs.com/lzj2023/p/17872391.html

相关文章

  • 代码随想录算法训练营第四天 | 24. 两两交换链表中的节点 19.删除链表的倒数第N个节
    LeetCode24.两两交换链表中的节点题目链接:LeetCode24思路:交换结点前将cur后第一个结点和第三个结点进行保存,然后修改cur指向头节点后再修改头节点后的结点classSolution{public:ListNode*swapPairs(ListNode*head){ListNode*dummyHead=newListNo......
  • 第二章 链表part01
    第二章链表part01203.移除链表元素  Code:/***Definitionforsingly-linkedlist.*structListNode{*  intval;*  ListNode*next;*  ListNode():val(0),next(nullptr){}*  ListNode(intx):val(x),next(nullptr){}*  L......
  • FreeRTOS--链表
    示例源码基于FreeRTOSV9.0.0链表1概述链表一般可分为单向链表、双向链表、环形链表。FreeRTOS采用的是环形双向链表设计;单向链表只有后继节点,双向链表有后继和前驱节点;链表的目的是把元素串联,其设计方式一般有两种:将元素放置在链表结构体中;将链表结构体放置在元素中;方......
  • [LeetCode Hot] LeetCode283. 移动零
    题目描述方法一:时间复杂度O(n2)classSolution{publicvoidmoveZeroes(int[]nums){for(inti=0;i<nums.length;i++){//指针i为0的时候停止if(nums[i]==0){//遍历[i+1,nums.length-1],如果遇......
  • [LeetCode Hot 100] LeetCode11. 盛最多的水
    题目描述方法一:暴力,超出时间限制模拟所有情况,记录最大的体积值。体积=Math.min(height[i],height[j])*(j-i)classSolution{publicintmaxArea(int[]height){intres=Integer.MIN_VALUE;for(inti=0;i<height.length;i++){......
  • 代码随想录算法训练营第三天 | 203.移除链表元素 707.设计链表 206.反转链表
    LeetCode 203.移除链表元素视频链接:LeetCode203思路:根据链表的性质,将目标值对应的节点保存在一个临时节点中,再重新设置cur下一个节点,再将临时节点进行删除classSolution{public:ListNode*removeElements(ListNode*head,intval){//删除头节点......
  • 数据结构与算法之单链表-----黑马程序员(26-35)
    1.链表的概念在计算机科学中,链表是数据元素的线性集合,其每个元素都指向下一个元素,元素储存上并不连续。 创建链表如图所示和相关代码publicclassdanlianbiao{privateNodehead=null;//头部第一个结点privatestaticclassNode{//后面的每个结点intvalue;Nodene......
  • #yyds干货盘点# LeetCode程序员面试金典:奇偶链表
    题目给定单链表的头节点head,将所有索引为奇数的节点和索引为偶数的节点分别组合在一起,然后返回重新排序的列表。第一个节点的索引被认为是奇数,第二个节点的索引为偶数,以此类推。请注意,偶数组和奇数组内部的相对顺序应该与输入时保持一致。你必须在O(1)的额外空间复杂......
  • #yyds干货盘点# LeetCode程序员面试金典:下一个更大元素 II
    题目给定一个循环数组nums(nums[nums.length-1]的下一个元素是nums[0]),返回nums中每个元素的下一个更大元素。数字x的下一个更大的元素是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的下一个更大的数。如果不存在,则输出-1。 ......
  • #yyds干货盘点# LeetCode程序员面试金典:下一个更大元素 II
    题目给定一个循环数组nums(nums[nums.length-1]的下一个元素是nums[0]),返回nums中每个元素的下一个更大元素。数字x的下一个更大的元素是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的下一个更大的数。如果不存在,则输出-1。 ......