算法题-链表03

08-回文链表

链接：234. 回文链表 - 力扣（LeetCode）

1. 题目描述

请判断一个链表是否为回文链表。

示例 1:

• 输入: 1->2
• 输出: false

示例 2:

• 输入: 1->2->2->1
• 输出: true

1. 思路

思路1（数组+双指针）：把链表按照原来的顺序放到一个数组，用双指针法，看数组是否回文

# 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 isPalindrome(self, head):""":type head: Optional[ListNode]:rtype: bool"""list = []while head:list.append(head.val)head = head.nextleft, right = 0, len(list)-1while left <= right:if list[left] != list[right]:return Falseleft += 1right -= 1return True

思路2：反转后半部分链表，反转后的链表，与前半部分链表进行比较

class Solution(object):def isPalindrome(self, head):""":type head: Optional[ListNode]:rtype: bool"""# 使用快慢指针法找到链表的中间节点fast = slow = head# 快指针每次移动两步，慢指针每次移动一步# 当快指针到达链表末尾时，慢指针正好位于链表中间while fast and fast.next:fast = fast.next.nextslow = slow.next# 初始化node为None，用于构建反转后的后半部分链表node = None# 反转后半部分链表# 从慢指针位置开始，将后半部分链表反转while slow:# 使用Python的多重赋值同时进行指针操作# slow.next指向node，实现反转# slow移动到原链表的下一个节点# node移动到当前slow节点（成为新的反转链表头）slow.next, slow, node = node, slow.next, slow# 比较前半部分链表和反转后的后半部分链表# 由于反转后的后半部分链表长度≤前半部分（整个），只需比较这部分即可while node:if node.val != head.val:return Falsenode = node.nexthead = head.nextreturn True

09-重排链表

链接：143. 重排链表 - 力扣（LeetCode）

1. 题目描述

1. 思路

思路1：利用双向队列，把所有元素存入，然后两头吐出来，以此重建链表

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
import collectionsclass Solution(object):def reorderList(self, head):""":type head: Optional[ListNode]:rtype: None Do not return anything, modify head in-place instead."""# 创建双向队列d = collections.deque()tmp = head# 将链表除了首元素外的所有节点加入双向队列while tmp.next:d.append(tmp.next)tmp = tmp.nexttmp = head  # 重置tmp指向链表头部# 交替从队列的尾部和头部取出节点，重新连接链表while len(d):# 从队列尾部取出节点（原链表的最后一个节点）tmp.next = d.pop()tmp = tmp.next# 如果队列中还有节点，从头部取出节点（原链表的第二个节点）if len(d):tmp.next = d.popleft()tmp = tmp.next# 将新链表的尾部节点的next置为None，防止形成环tmp.next = None

思路2：反转链表法，分隔两个链表，然链表的后半部分反转，然后再重建链表

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
import collectionsclass Solution(object):def reorderList(self, head):""":type head: Optional[ListNode]:rtype: None Do not return anything, modify head in-place instead."""# 处理空链表或单节点链表的特殊情况if head == None or head.next == None:return True  # 注意：这里应该是return而不是返回True，但原代码如此# 使用快慢指针找到链表中点slow, fast = head, headwhile fast and fast.next:slow = slow.nextfast = fast.next.next# 分割链表为左右两部分right = slow.next  # 右半部分slow.next = None  # 切断左右部分的连接# 反转右半部分链表right = self.reverseList(right)left = head  # 左半部分# 合并左右两部分：左半部分一定比右半边长，因此判断右半边即可while right:# 保存左半部分的下一个节点curLeft = left.next# 将当前左节点指向右节点left.next = right# 左指针移动到原左部分的下一个节点left = curLeft# 保存右半部分的下一个节点curRight = right.next# 将当前右节点指向左节点right.next = left# 右指针移动到原右部分的下一个节点right = curRight# 反转链表的辅助函数def reverseList(self, head):cur = headpre = Nonewhile cur != None:temp = cur.next  # 保存当前节点的下一个节点cur.next = pre  # 反转指针方向pre = cur  # 前驱节点移动到当前节点cur = temp  # 当前节点移动到下一个节点return pre  # 返回反转后的头节点