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