算法刷题笔记02:Linked List
2023-06-13 09:11:39 时间
Linked List
206.反转链表
题目描述
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
题目链接:https://leetcode-cn.com/problems/reverse-linked-list/
解法一:迭代
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
pre = None
cur = head
# 跳出循环条件
while cur:
# 暂存下个结点
temp_next = cur.next
# 将当前结点指向前一个值
cur.next = pre
# pre和cur都进一步
pre = cur
cur = temp_next
return pre
解法二:递归
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or head.next == None:
return head
res = self.reverseList(head.next)
# 将下个结点指向自己
head.next.next = head
# 避免链表循环
head.next = None
return res
24.两两交换链表中的节点
题目描述
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例 1:
输入:head = [1,2,3,4]
输出:[2,1,4,3]
题目链接:https://leetcode-cn.com/problems/swap-nodes-in-pairs
解法一:借用栈
class Solution(object):
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
# Linked List题目特殊情况处理
if not head or head.next == None:
return head
# dummy结点
p = ListNode(-1)
# 记录当前结点
cur = head
# 记录头结点.等到程序结束返回head.next即可
head = p
# 用stack保存每次迭代的两个节点
stack = []
while cur and cur.next:
# 栈入
stack.append(cur)
stack.append(cur.next)
# 当前结点移动2个位置
cur = cur.next.next
# 栈出操作,指向
p.next = stack.pop()
p.next.next = stack.pop()
# 移动p
p = p.next.next
# 边界条件判断,奇数时候会出现第一种情况,直接指向cur即可
if cur:
p.next = cur
else:
p.next = None
return head.next
解法二:迭代
class Solution(object):
def swapPairs(self, head):
# 增加一个特殊节点方便处理
p = ListNode(-1)
# 创建a,b两个指针,这里还需要一个tmp指针
a,b,p.next,tmp = p,p,head,p
while b.next and b.next.next:
# a前进一位,b前进两位
a,b = a.next,b.next.next
# 这步很关键,tmp指针用来处理边界条件的
# 假设链表是1->2->3->4,a指向1,b指向2
# 改变a和b的指向,于是就变成2->1,但是1指向谁呢?
# 1是不能指向2的next,1应该指向4,而循环迭代的时候一次处理2个节点
# 1和2的关系弄清楚了,3和4的关系也能弄清楚,但需要一个指针来处理
# 2->1,4->3的关系,tmp指针就是干这个用的
tmp.next,a.next,b.next = b,b.next,a
# 现在链表就变成2->1->3->4
# tmp和b都指向1节点,等下次迭代的时候
# a就变成3,b就变成4,然后tmp就指向b,也就是1指向4
tmp,b = a,a
return p.next
这里的迭代做法从 LeetCode 题解抄过来,感觉有点绕,涉及到了三个指针,不是很能理解。
解法三:递归
class Solution(object):
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
# 边界条件判断
if not head or head.next == None:
return head
# 从第3个链表往后进行交换
third = self.swapPairs(head.next.next)
# 从第3个链表往后都交换完了,我们只需要交换前两个链表即可,
# 这里我们把链表分为3组,分别是第1个节点,第2个节点,后面
# 的所有节点,也就是1→2→3,我们要把它变为2→1→3
second = head.next
head.next = third
second.next = head
return second
TODO
相关文章
- 大数据必学Java基础(五十四):List接口深入了解
- python中列表(list)函数及使用
- python基础(3)列表list[通俗易懂]
- 数组转换成list集合_字符串转数组js
- List转set_JAVA数组转set内容不一致
- ORA-01795: maximum number of expressions in a list is 1000 ORACLE 报错 故障修复 远程处理
- ORA-29879: cannot create multiple domain indexes on a column list using same indextype ORACLE 报错 故障修复 远程处理
- ORA-01590: number of segment free list (string) exceeds maximum of string ORACLE 报错 故障修复 远程处理
- ORA-01795: maximum number of expressions in a list is 1000 ORACLE 报错 故障修复 远程处理
- ORA-09943: Allocation of memory for password list component failed. ORACLE 报错 故障修复 远程处理
- ORA-14619: resulting List subpartition(s) must contain at least 1 value ORACLE 报错 故障修复 远程处理
- Redis List实现列表缓存的高效处理(credislist)
- 创建list ALV tree[RS_TREE_LIST_DISPLAY]详解编程语言
- Hibernate Query接口 list方法:返回查询结果的List集合
- List头文件助力Linux内核开发(list.hlinux)
- 长度查看Redis List长度:简单有效(redis查看list)
- Linux命令:学会使用List命令管理目录列表(linuxlist命令)
- Redis如何清空List:技巧分享(redis清空list)
- Mysql实现List存储的技巧(mysql存储list)
- 深入浅出Redis的List数据结构遍历(遍历redis list)
- Oracle数据库操作利用入参List实现批量处理(oracle入参list)
- 以List的形式将数据插入Redis(把list插入redis)
- 使用Redis实现List存储(向redis中存list)
- 使用Redis集合和List实现高效存储(redis集合和list)
- 使用Redis轻松获取List元素(redis 返回list)
- 基于C++list中erase与remove函数的使用详解
- 使用XmlSerializer序列化List对象成XML格式(list对象序列化)