链表（链表反转java）

链表（链表反转java）

1. 合并两个有序链表

牛客 力扣

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例一： 输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4] 示例二： 输入：l1 = [], l2 = [] 输出：[] 示例三： 输入：l1 = [], l2 = [0] 输出：[0]

题解：

哨兵节点的作用是方便得到最后的链表，即一个虚拟的头节点

from typing import Optional class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: # 设置哨兵节点（虚拟头结点），将较小的节点连接到这个哨兵节点，最后返回 prehead.next 即可 preHead = ListNode(-1) pre = preHead # pre 指针，用于连接链表（指针或游标） l1 = list1 l2 = list2 while l1 and l2: # 将值较小的的节点接到 pre 指针 if l1.val < l2.val: pre.next = l1 l1 = l1.next else: pre.next = l2 l2 = l2.next pre = pre.next # 节点移动 if l1: pre.next = l1 if l2: pre.next = l2 return preHead.next

参考：移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。   示例 1： 输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5] 示例 2： 输入：head = [], val = 1 输出：[] 示例 3： 输入：head = [7,7,7,7], val = 7 输出：[]   提示： 列表中的节点数目在范围 [0, 104] 内 1 <= Node.val <= 50 0 <= val <= 50

题解：

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def removeElements(self, head: ListNode, val: int) -> ListNode: dummy = ListNode(next=head) # 虚拟头结点或叫哨兵节点，它的下一个节点指向 head 头结点 cur = dummy # 相当于游标或指针，不断移动 while cur.next != None: if cur.next.val == val: cur.next = cur.next.next # 若等于目标元素，将 cur.next 指向下一个节点的 next，就实现了移除节点 else: cur = cur.next return dummy.next

3. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2] 输出：[2,1]

示例 3：

输入：head = [] 输出：[]

提示：

链表中节点的数目范围是 [0, 5000] -5000 <= Node.val <= 5000

题解一：双指针

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseList(self, head: ListNode) -> ListNode: cur = head # 头结点 pre = None # 前一个节点，初始为空 while cur != None: tmp = cur.next # 保存下一个节点 cur.next = pre # 反转，下一个节点指向前一个节点 # 更新节点 pre = cur # 移动 cur = tmp # 移动，相当于 cur = cur.next return pre # pre 最终会移动到最后一个节点，因此返回 pre 即可

题解二：递归法

class Solution: def reverseList(self, head: ListNode) -> ListNode: def reverse(pre, cur): if not cur: return pre tmp = cur.next cur.next = pre return reverse(cur, tmp) return reverse(None, head)

参考：翻转链表

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。