链表理论基础
文章链接：https://programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
C++的定义链表节点方式：
// 单链表
struct ListNode {
int val; // 节点上存储的元素
ListNode *next; // 指向下一个节点的指针
ListNode(int x) : val(x), next(NULL) {} // 节点的构造函数
};
ListNode* head = new ListNode(5);
// 或
ListNode* head = new ListNode();
head->val = 5;
python:
class ListNode:
def __init__(self, val, next=None):
self.val = val
self.next = next
C:
typedef struct ListNodeT {
int val;
struct ListNodeT next;
} ListNode;
删除节点
删除D节点，如图所示：
添加节点
如图所示：
性能分析
再把链表的特性和数组的特性进行一个对比，如图所示：
LeetCode203 移除链表元素
题目链接/文章讲解/视频讲解：：https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.htmlhttps://www.bilibili.com/video/BV1QB4y1D7ep )
增加虚拟头节点：
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def removeElements(self, head, val):
"""
:type head: ListNode
:type val: int
:rtype: ListNode
"""
newhead = ListNode(next = head)
current = newhead
while current.next:
if current.next.val == val: # 要删除的节点
current.next = current.next.next
else:
current = current.next
return newhead.next
增加虚拟头节点，可以对所有节点统一处理，如果不增加，需要对头节点和不是头节点的元素分别讨论
LeetCode707 设计链表
题目链接/文章讲解/视频讲解：
https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html
⭐定义节点ListNode具有数据val和next，同时MyLinkedList里面含一个计数器 方便插入删除
⭐注意边界
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
current = self.dummy_head.next # 指向next，index=0时直接指向head
for i in range(index):
current = current.next
return current.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:
current = self.dummy_head
while current.next:
current = current.next
current.next = ListNode(val)
self.size += 1
def addAtIndex(self, index: int, val: int) -> None:
if index < 0 or index > self.size:
return
# 插入current和current.next之间（第n个节点是current.next）
current = self.dummy_head
for i in range(index):
current = current.next
current.next = ListNode(val, current.next)
self.size += 1
def deleteAtIndex(self, index: int) -> None:
if index < 0 or index >= self.size:
return
# 通过操作current删除current.next（第n个节点是current.next）
current = self.dummy_head
for i in range(index):
current = current.next
current.next = current.next.next
self.size -= 1
# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)
LeetCode206 反转链表
双指针
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
current = head
pre = None # pre指向current前一个
while current: # 当current为null时停止遍历
tmp = current.next
current.next = pre # 改变方向
pre = current # per和current都向后移动一位
current = tmp
return pre # pre指向新链表头节点
