文章目录(Table of Contents)
基础知识
习题练习
链表翻转(考链表基本必考)
这一题是leetcode上第206题, 链接地址206. Reverse Linked List
这一题的要求很简单, 给定一个链表, 我们将其翻转即可. 可以查看下面的示例的输入和输出:
- Input: 1->2->3->4->5->NULL
- Output: 5->4->3->2->1->NULL
这里最简单的方法我们可以使用循环来完成, 即每次将这个节点的next指向他的上一个节点即可. 我们需要注意while中的顺序, 我们可以画图来理解一下其中的顺序, 大致的图是这样的.
其中following是记录cur后一个节点的, 这个是一定需要的.
- 因为我们下面一个步骤是修改cur.next=prev,
- 所以使用following保存原来的cur.next是很有必要的.
- # Definition for singly-linked list.
- # class ListNode:
- # def __init__(self, x):
- # self.val = x
- # self.next = None
- class Solution:
- def reverseList(self, head: ListNode) -> ListNode: # ListNode表示输出的数据结构
- cur, prev = head, None # 当前节点, 前驱节点
- while cur: # 最后一轮cur会变为None
- following = cur.next # 这个是一定需要的
- cur.next = prev
- prev = cur
- cur = following
- return prev
链表值两两交换
这一题是leetcode上第24题, 链接地址24. Swap Nodes in Pairs
这一题是要求翻转链表中相邻的两个节点的值, 输入和输出的范例如下所示:
- Given 1->2->3->4,
- Return the list as 2->1->4->3.
但是在做的时候, 我们需要考虑如下的特殊情况:
- 链表为空
- 链表里有一个值
- 链表元素为奇数的情况, 奇数的时候最后一个元素是不变的
我们有两种考虑的方式,
- 微信公众号
- 关注微信公众号
-
- QQ群
- 我们的QQ群号
-
评论