9/4 链表-力扣 234、19

234.回文链表

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

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

思考：链表遍历只能从前往后，为使能同时访问两端数据，创建一个列表去记录前部分数据

若只有一个节点，则直接返回true

将前部分值放入列表后，若有奇数个节点，则链表上的指针需再向后移一位；若为偶数个则不用

class Solution(object):def isPalindrome(self, head):""":type head: ListNode:rtype: bool"""if not head.next:return Truelength = 0p = headwhile p:length += 1p=p.nextmid = length // 2i = 0p = headl = []while i < mid:l.append(p.val)i += 1p = p.nextif length % 2 == 1:p = p.nexti = i - 1while p:if l[i] != p.val:return Falseelse:i -= 1p = p.nextreturn True

19、删除链表的倒数第N个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

 

示例 1：

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

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

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

思考：在链表中要删除哪个节点，就要去找它的前驱节点

1.当链表只有一个节点并且要删除倒数第一个节点时，直接返回空

2.当链表有n个节点要删除倒数第n个时，直接返回头节点的后续节点

3.last和pre同时指向头节点，用last节点先走n步，当该节点走到链尾时，pre节点即指向要删除节点的前驱节点

if not head.next and n == 1:return Nonep = headlen = 0while p:len += 1p = p.nextif len == n:return head.nextpre, last = head, headi = 0while i < n:last = last.nexti += 1while last.next:last = last.nextpre = pre.nextpre.next = pre.next.nextreturn head