数据结构02——链表

链表相关题目

01 移除链表元素（203）

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点。

#先构造一个节点指向head记录链表的头节点
class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy
        while head != None:
            if head.val == val:
                prev.next = head.next
            else:
                prev = head
            head = head.next
        return dummy.next

02 链表的中间结点(876)

给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

#链表的长度无法直接求出
class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        #无法直接求链表的长度，将链表的每一个元素存入数组
        a = [head]
        current = head
        while current != None and current.next !=0:
            current = current.next
            a.append(current)
       
        n = len(a)//2
        current2 = head
        num = 0
        if len(a)%2 == 1:
            while num < n:
                current2 = current2.next
                num +=1
            return current2
        else:
            while num < n-1:
                current2 = current2.next
                num +=1
            return current2

03 删除链表的倒数第 N 个结点（19）

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？

#方法一：先求出链表的长度再删除
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0,head)
        def getLength(head):
            length = 0
            while head :
                length += 1
                head = head.next
            return length
        L = getLength(head)
        current = dummy
        for i in range(1,L+1-n):
            current = current.next
        current.next = current.next.next
        return dummy.next

#方法2给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
#快慢指针的方法
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0,head)
        slow = dummy
        first = head
        for i in range(n):
            first = first.next
        while first:
            first = first.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy.next