链表0805

0203. 移除链表元素

**给你一个链表的头节点 **head 和一个整数 val ，请你删除链表中所有满足 Node.val == 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
 输出：[]

** **提示：

• **列表中的节点数目在范围 **[0, 104] 内
• 1 <= Node.val <= 50
• 0 <= val <= 50

题解：

 # Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, val=0, next=None):
 #         self.val = val
 #         self.next = next
 class Solution:
     def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
         dummy = ListNode(0)
         dummy.next = head
         current = dummy
         #创建了虚拟头结点
         while current and current.next:
             if current.next.val==val:
                 current.next=current.next.next
             else : current=current.next
         return dummy.next
         

这里创建了虚拟头结点，目的就是为了方便删除头结点的情况，便于统一管理所有结点

0328. 奇偶链表

**给定单链表的头节点 **head ，将所有索引为奇数的节点和索引为偶数的节点分别分组，保持它们原有的相对顺序，然后把偶数索引节点分组连接到奇数索引节点分组之后，返回重新排序的链表。

第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。

请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

**你必须在 **O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

---

示例 1:

 输入: head = [1,2,3,4,5]
 输出: [1,3,5,2,4]

示例 2:

 输入: head = [2,1,3,5,6,4,7]
 输出: [2,3,6,7,1,5,4]

---

提示:

• n == 链表中的节点数
• 0 <= n <= 104
• -106 <= Node.val <= 106

题解：

 # Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, val=0, next=None):
 #         self.val = val
 #         self.next = next
 class Solution:
     def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
         if not head or not head.next:
             return head
         odd = 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.next
 
         # 连接奇数链尾部到偶数链头
         odd.next = even_head
         return head

很容易想到快慢指针，但是要先保存偶数链起点的引用，不然就容易丢失

0234. 回文链表

**给你一个单链表的头节点 **head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

 输入：head = [1,2,2,1]
 输出：true

示例 2：

 输入：head = [1,2]
 输出：false

题解：

 # Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, val=0, next=None):
 #         self.val = val
 #         self.next = next
 class Solution:
     def isPalindrome(self, head: Optional[ListNode]) -> bool:
         # 特殊情况：空链表或只有一个节点，必然是回文
         if not head or not head.next:
             return True
         dummy=ListNode(0)
         dummy.next=head
         left,right=dummy,dummy
         while right and right.next:
             right=right.next.next
             left=left.next
         current=head
         second_half_list = []
         while left.next:
             
             second_half_list.append(left.next.val)
             left = left.next
         while second_half_list:
             if current.val != second_half_list.pop():
                 return False
             current = current.next
 
         return True
                      
 

其实可以直接将整个链表转换成列表，然后用双指针判断是否为回文。

也可以构造辅助函数，实现原地翻转，这样的空间复杂度是 O(1)。

 # 反转链表的辅助函数
     def reverse(self, head: Optional[ListNode]) -> Optional[ListNode]:
         prev = None
         curr = head
         while curr:
             next_temp = curr.next
             curr.next = prev
             prev = curr
             curr = next_temp
         return prev