作者： 千石
支撑：点赞、收藏、谈论
欢迎各位在谈论区沟通
前语
本文内容来自我平常学习的一些积累，如有过错，还请纠正
在标题实战部分，我将代码完成和代码解说设置在了解题思路的下方，方便各位作为参阅刷题
一些话
本文内容来自我平常学习的一些积累，如有过错，还请纠正
在标题实战部分，我将代码完成和代码解说设置在了解题思路的下方，方便各位作为参阅刷题
标题操练过程：
- 给自己10分钟，读题并考虑解题思路
- 有了思路今后开端写代码，假如在上一过程中没有思路则停止考虑并且看该题题解
- 在看懂题解（暂时没看懂也没关系）的思路后，背诵默写题解，直至能熟练写出来
- 隔一段时刻，再次尝试写这道标题
刷题
707. 规划链表 – 力扣（LeetCode）
题意：
在链表类中完成这些功能：
- get(index)：获取链表中第index个节点的值。假如索引无效，则回来-1。
- addAtHead(val)：在链表的第一个元素之前添加一个值为val的节点。刺进后，新节点将成为链表的第一个节点。
- addAtTail(val)：将值为val 的节点追加到链表的最终一个元素。
- addAtIndex(index,val)：在链表中的第index个节点之前添加值为val 的节点。假如index等于链表的长度，则该节点将附加到链表的结尾。假如 index 大于链表长度，则不会刺进节点。假如index小于0，则在头部刺进节点。
- deleteAtIndex(index)：假如索引index 有用，则删除链表中的第index 个节点。
题解
- 关于 get(index) 方法，咱们需求遍历链表，找到第 index 个节点，然后回来该节点的值。假如 index 小于 0 或大于等于链表长度，则回来 -1。时刻复杂度为 O(n)，其间 n 是链表的长度。
- 关于 addAtHead(val) 方法，咱们需求创立一个新的节点，并将它的 next 指针指向本来的头节点。然后将头节点指向新的节点。时刻复杂度为 O(1)。
- 关于 addAtTail(val) 方法，咱们需求遍历整个链表，找到最终一个节点，然后将其 next 指针指向一个新的节点。时刻复杂度为 O(n)。
- 关于 addAtIndex(index, val) 方法，咱们需求遍历链表，找到第 index-1 个节点。然后咱们创立一个新的节点，并将其 next 指针指向第 index 个节点。最终将第 index-1 个节点的 next 指针指向新的节点。时刻复杂度为 O(n)，其间 n 是链表的长度。
- 关于 deleteAtIndex(index) 方法，咱们需求遍历链表，找到第 index-1 个节点，然后将它的 next 指针指向第 index+1 个节点。时刻复杂度为 O(n)，其间 n 是链表的长度。
代码完成如下：
# 界说链表节点类
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 界说链表类
class MyLinkedList:
def __init__(self):
"""
在此处初始化你的数据结构。
"""
self.head = None
self.tail = None
self.length = 0
def get(self, index: int) -> int:
"""
获取链表中第 index 个节点的值。假如索引无效，则回来-1。
"""
if index < 0 or index >= self.length:
return -1
cur = self.head
for i in range(index):
cur = cur.next
return cur.val
def addAtHead(self, val: int) -> None:
"""
在链表的最初刺进一个值为 val 的节点。刺进后，新节点将成为链表的第一个节点。
"""
new_node = ListNode(val)
if not self.head:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head = new_node
self.length += 1
def addAtTail(self, val: int) -> None:
"""
将值为 val 的节点追加到链表的最终一个元素。
"""
new_node = ListNode(val)
if not self.head:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_node
self.length += 1
def addAtIndex(self, index: int, val: int) -> None:
"""
在链表中的第 index 个节点之前添加值为 val 的节点。假如 index 等于链表的长度，则该节点将附加到链表的结尾。假如 index 大于链表长度，则不会刺进节点。
"""
if index > self.length:
return
if index <= 0:
self.addAtHead(val)
elif index == self.length:
self.addAtTail(val)
else:
new_node = ListNode(val)
cur = self.head
for i in range(index - 1):
cur = cur.next
new_node.next = cur.next
cur.next = new_node
self.length += 1
def deleteAtIndex(self, index: int) -> None:
"""
假如索引有用，则删除链表中的第 index 个节点。
"""
if index < 0 or index >= self.length:
return
if index == 0:
self.head = self.head.next
if not self.head:
self.tail = None
else:
cur = self.head
for i in range(index - 1):
cur = cur.next
cur.next = cur.next.next
if index == self.length - 1:
self.tail = cur
self.length -= 1
206. 回转链表 – 力扣（LeetCode）
题意：回转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
题解
本题比较简单，有多种方法能够解决，这里介绍两种： 迭代方法：
- 界说两个指针，一个指向当时节点，一个指向前一个节点，初始化为None。
- 循环遍历链表，将当时节点的next指针指向前一个节点。
- 将前一个节点指针和当时节点指针都向后移动一个节点。
- 当当时节点为None时，遍历完毕，回来新的头节点。
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
递归方法：
- 递归到链表尾部，回来新的头节点。
- 将当时节点的next节点的next指针指向当时节点，将当时节点的next指针置为None。
- 回来新的头节点。
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
new_head = self.reverseList(head.next)
head.next.next = head
head.next = None
return new_head
24. 两两交流链表中的节点 – 力扣（LeetCode）
题解
- 界说一个虚拟节点 dummy，指向链表头节点，用于链表交流时记载新的头节点。
- 界说两个指针 prev 和 curr，别离指向需求交流的相邻节点的前一个节点和当时节点。
- 循环遍历链表，假如当时节点和下一个节点不为空，则进行交流，交流完后需求更新 prev 和 curr 的方位。
- 回来新的头节点，即 dummy.next。
代码完成如下
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
# 界说虚拟节点，方便链表操作
dummy = ListNode(-1)
dummy.next = head
prev = dummy
curr = head
while curr and curr.next:
next_node = curr.next
prev.next = next_node
curr.next = next_node.next
next_node.next = curr
prev = curr
curr = curr.next
return dummy.next
