链表理论基础
链表的类型
单链表
每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。
链表的入口节点称为链表的头结点也就是head。
双链表
单链表中的指针域只能指向节点的下一个节点。
双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。
双链表 既可以向前查询也可以向后查询。
循环链表
循环链表，顾名思义，就是链表首尾相连。
循环链表可以用来解决约瑟夫环问题。
链表的存储方式
数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。
链表是通过指针域的指针链接在内存中各个节点。
所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。
链表的定义
class ListNode:
def __init__(self, val, next=None):
self.val = val
self.next = next203.移除链表元素
力扣题目链接(opens new window)
题意：删除链表中等于给定值 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 输出：[]
代码
学过链表操作，因此直接在看一遍代码后跳过
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:
while head is not None and head.val == val:
head = head.next
if head is None:
return head
cur = head
while (cur.next != None):
if (cur.next.val == val):
cur.next = cur.next.next # 删除cur.next节点
else:
cur = cur.next
return head
707.设计链表
力扣题目链接(opens new window)
题意：
在链表类中实现这些功能：
-
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
-
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
-
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
-
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
-
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
代码
照着给的默写了一遍，应该是会了
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class MyLinkedList:
def __init__(self):
self.dummy_head = ListNode()
self.size = 0
def get(self, index: int) -> int:
if index < 0 or index >= self.size:
return -1
cur = self.dummy_head.next
for _ in range(index):
cur = cur.next # cur指向index位置
return cur.val
def addAtHead(self, val: int) -> None:
self.dummy_head.next = ListNode(val, self.dummy_head.next)
self.size += 1
def addAtTail(self, val: int) -> None:
cur = self.dummy_head
while cur.next:
cur = cur.next # cur指向最后一个节点
cur.next = ListNode(val)
self.size += 1
def addAtIndex(self, index: int, val: int) -> None:
if index < 0 or index > self.size: # index大于size时，相当于在尾部插入节点
return
cur = self.dummy_head
for _ in range(index):
cur = cur.next
cur.next = ListNode(val, cur.next) # 在cur和cur.next之间插入节点
self.size += 1
def deleteAtIndex(self, index: int) -> None:
if index < 0 or index >= self.size:
return
cur = self.dummy_head
for _ in range(index): # cur指向index位置的前一个节点
cur = cur.next
cur.next = cur.next.next
self.size -= 1
#代码随想录算法训练营/第三天/206.反转链表 #算法/链表
206.反转链表
力扣题目链接(opens new window)
题意：反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
代码
我一开始是想着建立两个链表，然后又想到了递归，直到这里给了个双指针法，当然递归也能做。这里用的是递归哦。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
return self.reverse(None, head)
def reverse(self, pre: ListNode, cur: ListNode) -> ListNode:
if cur is None: # 递归终止条件,如果pre为空，则说明已经到达链表尾部，返回pre
return pre
# 将当前节点的next指针指向pre
temp = cur.next
cur.next = pre
# temp.next = cur 因为temp可能是None所以需要遍历
return self.reverse(cur, temp)