算法|Leetcode刷题笔记之: 链表（单链表经典题目）链表|指针|leetcode|单链表|算法

这里写目录标题

206. 反转链表
- 迭代算法:
- 递归算法
[203. 移除链表元素](https://leetcode-cn.com/problems/remove-linked-list-elements/)
[328. 奇偶链表](https://leetcode-cn.com/problems/odd-even-linked-list/)
[234. 回文链表](https://leetcode-cn.com/problems/palindrome-linked-list/)
总结

206. 反转链表迭代算法: pre, cur一前一后两个指针，cur指向pre，pre成了cur，cur成cur.next。
画图即可。

# 迭代的解法 class Solution: def reverseList(self, head: ListNode) -> ListNode: # 初始化 pre = None cur = head while cur: # cur.next 指向 pre # prev 变为cur # cur 变为cur_next（提前存储） cur_next = cur.next cur.next = pre pre = cur cur = cur_next return pre

递归算法递归算法的流程，假设部分流程已经完成。
假设:
1 -> 2 -> 3 -> 4 -> 5
部分完成后:
1 -> [ 2 <- 3 <- 4 <- 5]
我们希望 3.next指向2，而3是2.next，所以是2.next.next = 2
那什么时候停止呢？
null <- [1 <- 2 <-3 <- 4 <- 5]
即1.next = null

# 递归的解法 class Solution: def reverseList(self, head: ListNode) -> ListNode: # 当None或者只有一个节点，返回自身 if not head or not head.next: return head # 从head.next开始反转，注意reverseList返回的是头结点，所以这里返回的其实是reversed_head的头结点，即原始链表的最后一个节点 reversed_head =self.reverseList(head.next) # 现在head.next指向的是reversed_head的尾结点，我们让这个尾结点指向head head.next.next = head # 注意上面指向完毕后，我们要确保链表的尾结点指向None，不然就是尾部两个节点互指了 head.next = None return reversed_head

203. 移除链表元素 【算法|Leetcode刷题笔记之: 链表（单链表经典题目）】这道题乍一眼看上去很简单，遍历链表，遇到符合条件的直接指向删除操作即可，注意有几个坑:

我们需要设置两个指针，这两个指针一开始不能是要删除的点，所以在开始之前先把开头的要删除的点都删除干净
后序就是正常删除操作

class Solution: def removeElements(self, head: ListNode, val: int) -> ListNode: if not head: return # 先排查头结点的值，不然后面会比较麻烦 while head and head.val == val: head = head.next # 上一步可能会导致head为空，所以这里要加一个判断 if head: pre = head cur = head.next while cur and pre: if cur.val == val: # val相同，则改变pre指向和cur的位置 pre.next = cur.next cur = cur.next else: # val不同，则pre,cur位置均往前一步 pre = pre.next cur = cur.next return head

328. 奇偶链表构建两个表头，一个奇数表头以head为头结点，一个偶数表头以head.next为头结点，先更新奇点，在更新偶数点，每次更新完后对应指针指向刚被更新过的点上。注意这里的循环停止条件，画图便可以发现，如果最后一个节点是偶数点（即even.next为None）或者最后一个点为奇数点(even为None)两表构建完成。

class Solution: def oddEvenList(self, head: ListNode) -> ListNode: if not head or not head.next: return headodd = head even = head.next even_head = even while even and even.next: # 更新奇点 odd.next = even.next odd = odd.next # 更新偶点 even.next = odd.next even = even.nextodd.next = even_head return head

234. 回文链表我的第一想法，使用递归，比较头结点和尾结点的值，然后比较递归计算去掉首尾的链表。这样子是可行的，但是却没有通过链表很长的case

class Solution: def isPalindrome(self, head: ListNode) -> bool: # 空结点或者单节点返回True if not head or not head.next: return True # 设置三个指针，分别指向头结点，倒数第二个结点，尾结点 first = head second_last = head last = second_last.next while last.next: second_last = second_last.next last = second_last.next # 比较头尾结点 if first.val != last.val: return False # 删除尾结点，递归比较去掉头结点和尾结点的链表是否为回文链表 second_last.next = None return self.isPalindrome(head.next)

然后，有一种优化的方法便是，把后半部分的链表翻转，然后直接比较即可。

class Solution: def isPalindrome(self, head: ListNode) -> bool: def reverseList(head): pre = None cur = head while cur: cur_next = cur.next cur.next = pre pre = cur cur = cur_next return pre# 计算链表长度 length = 0 temp = head while temp: temp = temp.next length += 1 # 指针至于后半部分链表的头结点 head1 = head for _ in range(length//2): head1 = head1.next# 后半部分镜像链表经过翻转后应该与前半部分一样 head1 = reverseList(head1) # 比较前后两半链表 for _ in range(length//2): if head.val != head1.val: return False head = head.next head1 = head1.next return True

总结