目录
链表理论基础
链接：代码随想录
学习时间：20分钟
LeetCode203. 移除链表元素
先举个例子，这里以链表 1 4 2 4 来举例，移除元素4。
注意的点：关于清理内存
如果使用C，C++编程语言的话，不要忘了还要从内存中删除这两个移除的节点， 清理节点内存之后如图：
当然如果使用java ，python的话就不用手动管理内存了。
还要说明一下，就算使用C++来做leetcode，如果移除一个节点之后，没有手动在内存中删除这个节点，leetcode依然也是可以通过的，只不过，内存使用的空间大一些而已，但建议依然要养成手动清理内存的习惯。
方法一： 直接在原来的链表上进行删除操作
1. 思路
这种情况下的移除操作，就是让节点next指针直接指向下下一个节点就可以了，
那么因为单链表的特殊性，只能指向下一个节点，刚刚删除的是链表的中第二个，和第四个节点，那么如果删除的是头结点又该怎么办呢？
移除头结点和移除其他节点的操作是不一样的，因为链表的其他节点都是通过前一个节点来移除当前节点，而头结点没有前一个节点。所以头结点如何移除呢，其实只要将头结点向后移动一位就可以，这样就从链表中移除了一个头结点。
总结，这种情况需要把删除头节点的情况单独拎出来讨论。
2. 代码实现
#Apprach 1：dicuss the headnode
#complexity analysis: time O(N) space O(1)
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
# 不用虚拟头节点的情况
# time：O(N);space：O(1)
class Solution(object):
def removeElements(self, head, val):
"""
:type head: ListNode
:type val: int
:rtype: ListNode
"""
# 处理头结点，注意要使用while
while ( head!=None and head.val == val):
head = head.next
cur = head
while cur != None and cur.next != None:
if cur.next.val != val:
cur = cur.next
else:
# 这里不用让cur指向下一个元素，cur是处理cur.next的
# 现在cur.next已经变了
cur.next = cur.next.next
return head
3. 复杂度分析
时间复杂度：O(N）
总体来说是指针从头到尾遍历一遍链表进行处理，所以时间复杂度为O(N）；
空间复杂度：O(1）
只储存了几个常数级别的指针在内存中。
4. 思考
- 在处理head节点的时候，只能用while不能用if。出错实例：【7,7,7,7】val为7，这样子会漏掉第二个元素未处理，如果刚好为val值则会报错；
- 处理非head节点的时候，else后面的语句不可以直接拿出来和if平齐。出错实例：【1,2,2,1】val为2。这样子会漏掉val值后面的值未处理，如果val值后面的值也为val值就会出错；
- 处理非头节点的时候，更新 cur.next 之后，不需要让cur指向下一个元素，因为cur是用来处理cur.next的，现在cur.next已经变了。
- 这种将头节点分开讨论的方法显得代码有些冗余。
方法二：设置一个虚拟头节点
1. 思路
第一种思路会发现，需要单独写一段逻辑来处理移除头结点的情况。那么可不可以 以一种统一的逻辑来移除 链表的节点呢。其实可以设置一个虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行移除了。来看看如何设置一个虚拟头。依然还是在这个链表中，移除元素1。
这里来给链表添加一个虚拟头结点为新的头结点，此时要移除这个旧头结点元素1。这样是不是就可以使用和移除链表其他节点的方式统一了呢？来看一下，如何移除元素1 呢，还是熟悉的方式，然后从内存中删除元素1。
最后呢在题目中，return 头结点的时候，别忘了 return dummyNode->next;， 这才是新的头结点
2. 代码实现
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
# 使用虚拟头节点的情况
# time:O(n);space:O(1)
class Solution(object):
def removeElements(self, head, val):
"""
:type head: ListNode
:type val: int
:rtype: ListNode
"""
dummyNode = ListNode()
dummyNode.next = head
cur = dummyNode
while cur != None and cur.next != None:
if cur.next.val != val:
cur = cur.next
else:
cur.next = cur.next.next
return dummyNode.next
3. 复杂度分析
时间复杂度：O(N）
总体来说是指针从头到尾遍历一遍链表进行处理，所以时间复杂度为O(N）；
空间复杂度：O(1）
只储存了几个常数级别的指针在内存中。
4. 思考
- 添加虚拟头节点是链表中很常见的技巧，可以简化代码实现中需要讨论的情况。
reference：代码随想录 (programmercarl.com)
本题学习时间：90分钟。
LeetCode707.设计链表
1. 思路
这五个接口，已经覆盖了链表的常见操作，是练习链表操作非常好的一道题目
链表操作的两种方式：
- 直接使用原来的链表来进行操作。
- 设置一个虚拟头结点在进行操作。
下面采用的设置一个虚拟头结点，这道题目设计链表的五个接口：
- 获取链表第index个节点的数值
- 在链表的最前面插入一个节点
- 在链表的最后面插入一个节点
- 在链表第index个节点前面插入一个节点
- 删除链表的第index个节点
删除链表节点
添加链表节点
这道题可以有两种实现方式，第一种是单链表，第二种是双链表。
2. 代码实现一（单链表）
# 看解析之后写的
# 需要自己定义linknode
class LinkNode():
def __init__(self,val):
self.val = val
self.next = None
class MyLinkedList(object):
def __init__(self):
self.dummyHead = LinkNode(0)
self.size = 0
# 1. 获取第N个节点的数值
# time：O(N);space:O(1)
def get(self, index):
"""
:type index: int
:rtype: int
"""
# 非法判断
if index<0 or index >=self.size:
return -1
# 初始化cur
cur = self.dummyHead.next
# 根据index去移动cur
while index:
cur = cur.next
index -= 1
return cur.val
# 2. 头部插入节点
# time:O(N);space:O(1)
def addAtHead(self, val):
"""
:type val: int
:rtype: None
"""
# 这里都不需要return什么
self.addAtIndex(0,val)
# 3. 尾部插入节点
# time:O(N);space:O(1)
def addAtTail(self, val):
"""
:type val: int
:rtype: None
"""
# 这里都不需要return什么
self.addAtIndex(self.size,val)
# 4. 第index个节点之前插入节点
# time:O(N);space:O(1)
def addAtIndex(self, index, val):
"""
:type index: int
:type val: int
:rtype: None
"""
if index<0: index = 0
if index>self.size: return
self.size += 1
newNode = LinkNode(val)
pre = self.dummyHead
cur = self.dummyHead.next
# 把pre和cur移动到合适的位置
while index:
pre = pre.next
cur = cur.next
index -= 1
# 开始变化元素指针方向了
newNode.next = cur
pre.next = newNode
# 这里都不需要return什么
# 5. 删除第index个节点
# time:O(N);space:O(1)
def deleteAtIndex(self, index):
"""
:type index: int
:rtype: None
"""
if 0 <= index < self.size:
# 初始化cur指针,pre指针
pre = self.dummyHead
cur = self.dummyHead.next
self.size -= 1
while index:
pre = pre.next
cur = cur.next
index -= 1
# 开始删除cur指向的元素的下一个了
pre.next = cur.next
# 这里都不需要return什么
# 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)
跟以上的代码几乎一样，但是感觉更精简一点的代码如下：
class Node():
def __init__(self,val,):
self.val = val
self.next = None
class MyLinkedList(object):
#Approach1: single link list
def __init__(self):
self._head = Node(0) #本来就是虚拟头结点了,这里不可以写成None
self._size = 0
#complexity analysis: time O(N) space O(1)
def get(self, index):
"""
:type index: int
:rtype: int
"""
#记住这种连着写的写法
if 0<= index < self._size:
node = self._head
for i in range(index+1):
node = node.next
return node.val
else:
return -1
def addAtHead(self, val):
"""
:type val: int
:rtype: None
"""
self.addAtIndex(0,val)
def addAtTail(self, val):
"""
:type val: int
:rtype: None
"""
self.addAtIndex(self._size,val)
#complexity analysis: time O(N) space O(1)
def addAtIndex(self, index, val):
"""
:type index: int
:type val: int
:rtype: None
"""
if index <0:
index = 0
if index > self._size:
return
self._size += 1
add_node = Node(val)
prv_node,cur_node = None,self._head
for _ in range (index+1):
prv_node,cur_node = cur_node,cur_node.next
if 0<= index <= self._size:
prv_node.next,add_node.next = add_node,cur_node
#complexity analysis: time O(N) space O(1)
def deleteAtIndex(self, index):
"""
:type index: int
:rtype: None
"""
if index <0 or index >= self._size:
return
else:
self._size -= 1
prv_node,cur_node = None,self._head
for _ in range(index+1):
prv_node,cur_node = cur_node,cur_node.next
prv_node.next = cur_node.next
# 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)
3. 复杂度分析
- def get(self, index): 时间复杂度O(N）；空间复杂度：O（1）
需要根据index的值遍历到合适的位置再做相应的操作，因此time：O(N），空间上只有几个指针占用的空间，space：O(1)
- def addAtIndex(self, index, val): 时间复杂度：O(N）；空间复杂度：O(1）
需要根据index的值把pre和cur指针遍历到合适的位置再做相应的操作，因此time：O(N），空间上只有几个指针占用的空间，space：O(1）
- def addAtHead(self, val): 时间复杂度：O(N）；空间复杂度：O(1）
调用的addAtIndex(self, index, val)函数，时空复杂度一致
- def addAtTail(self, val):时间复杂度：O(N）；空间复杂度：O(1）
调用的addAtIndex(self, index, val)函数，时空复杂度一致
- def deleteAtIndex(self, index):时间复杂度：O(N）；空间复杂度：O(1）
需要根据index的值遍历到合适的位置再做相应的操作，因此time：O(N），空间上只有几个指针占用的空间，space：O(1)
4. 思考
- 注意定义节点和单链表的形式，节点包括val和next；单链表包括self._head和self._size；
- Python中条件可以连着写 0≤ index<size 这样；
- 巧妙的同时定义两个node，分别是current and prev ，并且可以把所有边界情况包含进去；
- 一边画图一边举例子写代码的话，更加不容易出错~
Reference：
本题学习时间：75分钟。
LeetCode206. 反转链表
方法一：双指针法（迭代）
1. 思路
如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。其实只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表，如图所示:
之前链表的头节点是元素1， 反转之后头结点就是元素5 ，这里并没有添加或者删除节点，仅仅是改变next指针的方向。
那么接下来看一看是如何反转的呢？
首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。
然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。（为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。）
接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。
最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点。
2. 代码实现
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
# time:o(N);space:O(1)
class Solution(object):
def reverseList(self, head):
preNode = None
curNode = head
while curNode:
tmpNode = curNode.next
# 改变指向
curNode.next = preNode
# 更新指针
preNode = curNode
curNode = tmpNode
return preNode
# 如果head直接为空，return的直接是None，包含在情况里
# 如果链表只有head一个元素，preNode最后指向的也是head，包含在情况里
# 链表有两个及以上元素，常规情况
3. 复杂度分析
时间复杂度：O(N)
三个指针要一起把这个链表从头到尾遍历一边，时间复杂度为O(N）；
空间复杂度：O(1）
只是储存了常数级的几个指针而已。
4. 思考
- 本题的整体思路上不难，但是有不少需要注意的细节，如果出现问题的话，就会造成死循环或者其他错误；
- 在有了大体的思路之后，具体执行的时候，我们会发现我们需要另一个指针tmpNode去保存之前的cur.next指向的Node，因为cur指针方向改变之后，我们会找不到cur原先next的那个Node，需要趁着没赋值的时候保存之；
- pre和next合适的初始化，可以避免讨论head为空或者链表只有head这一个元素的类似边界情况，或者可以先讨论，等一般情况下的代码写好之后，再代入特殊情况精简代码；
- while的循环条件是本题一个需要仔细考虑的问题，一般都是模拟这个思路去走一遍，看看走到最后该结束的时候，各个变量在那时候的状态；
- 在更新cur和pre指针的时候，顺序是不可以改变的，因为如果cur先赋值之后，当pre要赋值的时候cur会找不到了。
方法二：递归写法
1. 思路
递归法相对抽象一些，但是其实和双指针法是一样的逻辑，同样是当cur为空的时候循环结束，不断将cur指向pre的过程。
关键是初始化的地方，可能有的同学会不理解， 可以看到双指针法中初始化 cur = head，pre = NULL，在递归法中可以从如下代码看出初始化的逻辑也是一样的，只不过写法变了。具体可以看代码（已经详细注释），双指针法写出来之后，可以照着写递归的代码，代码逻辑都是一样的。
2. 代码实现
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
# time:O(N);space:O(N)
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
def reverse(preNode,curNode):
# base case
if curNode == None: return preNode
# 反转指向
tmpNode = curNode.next
curNode.next = preNode
return reverse(curNode,tmpNode)
# 初始化PreNode和curNode
return reverse(None,head)
3. 复杂度分析
时间复杂度：O(N)
其中 N 是链表的长度，需要对链表的每个节点进行反转操作。
空间复杂度：O(N）
其中 N 是链表的长度，空间复杂度主要取决于递归调用的栈空间，最多为 N 层。
4. 思考
- 递归法实际上也就全部是双指针的逻辑，只是换成了递归的写法而已；
- 建议将双指针练习的非常熟悉时候，再来直接写递归的代码。
Reference：
本题学习时间：60分钟。
PS： 本篇通过设计链表练习了链表的基本操作，在移除链表元素中理解了虚拟头节点的技巧，在反转链表中学习了双指针法及其递归写法；有些绕但整体难度不大；所花时间4小时。