[数据结构与算法]链表部分算法题（代码随想录）

链表

1.移除链表元素

题目链接

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

虚拟头结点很重要

直接使用原来的链表来进行删除操作

def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
    while head is not None and head.val == val:
        head = head.next
    if head is None:
        return head
    cur = head
    nxt = head.next
    while nxt is not None:
        if nxt.val == val:
            cur.next = nxt.next
            nxt = cur.next
        else:
            cur = nxt
            nxt = nxt.next
    return head

设置一个虚拟头结点在进行删除操作

def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
    hv = ListNode(next=head)
    cur = hv
    while cur.next is not None:
        if cur.next.val == val:
            cur.next = cur.next.next
        else:
            cur = cur.next
    return hv.next

2.设计链表

题目链接

虚拟头结点很重要

class Node:
    def __init__(self,val):
        self.val = val
        self.next = None

class MyLinkedList:

    def __init__(self):
        self.head = Node(0)
        self.count = 0

    def get(self, index: int) -> int:
        if index >= self.count or index < 0:
            return -1
        cnt = 0
        cur = self.head
        while cnt <= index:
            cur = cur.next
            cnt += 1
        return cur.val

    def getNode(self, index: int) -> Node:
        if index >= self.count:
            return None
        cnt = 0
        cur = self.head
        while cnt <= index:
            cur = cur.next
            cnt += 1
        return cur

    def addAtHead(self, val: int) -> None:
        node = self.head.next
        newNode = Node(val)
        self.head.next = newNode
        newNode.next = node
        self.count += 1

    def addAtTail(self, val: int) -> None:
        tail = self.getNode(self.count - 1)
        newNode = Node(val)
        tail.next = newNode
        self.count += 1

    def addAtIndex(self, index: int, val: int) -> None:
        if index == self.count:
            self.addAtTail(val)
        elif index > self.count:
            return
        elif index < 0:
            self.addAtHead(val)
        else:
            node = self.getNode(index - 1)
            newNode = Node(val)
            nxt = node.next
            node.next = newNode
            newNode.next = nxt
            self.count += 1


    def deleteAtIndex(self, index: int) -> None:
        if index >= self.count or index < 0:
            return
        pre = None
        if index == 0:
            pre = self.head
        else:
            pre = self.getNode(index-1)
        pre.next = pre.next.next
        self.count -= 1

    def print(self) -> None:
        cnt = 0
        cur = self.head
        while cnt <= self.count-1:
            cur = cur.next
            print(str(cur.val) + " ")
            cnt += 1

3.反转链表

题目链接

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

使用头插法

def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    if head is None or head.next is None:
        return head
    hv = ListNode(next=head)
    cur = hv.next.next
    head.next = None
    while cur is not None:
        next = cur.next

        hv.next = cur
        cur.next = head
        head = cur
        cur = next
    return hv.next

逐个改变next

def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    pre = None # pre = head ×
    cur = head # cur = head.next ×
    while cur is not None:
        temp = cur.next  # 暂存cur的下一个节点
        cur.next = pre # cur的next指向前一个结点
        pre = cur # 将下一轮的pre变为cur
        cur = temp # 将下一轮的cur变为cur.next
    return pre

4.两两交换链表中的节点(2)

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

自己AK的

def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
    if head is None or head.next is None:
        return head
    pre = head
    cur = head.next

    temp = cur.next
    cur.next = pre

    pre.next = self.swapPairs(temp)
    return cur

非递归版本

def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
    hv = ListNode(next=head)
    temp = hv
    while temp.next is not None and temp.next.next is not None:
        pre = temp.next
        cur = temp.next.next

        temp.next = cur
        pre.next = cur.next
        cur.next = pre
        temp = pre
    return hv.next

5.删除链表的倒数第 N 个结点

递归写法

应该没问题的吧 自测过

count = 0

def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
    hv = ListNode(next=head)
    cur = hv
    self.remove(cur,cur.next,n)
    return hv.next

def remove(self,pre: Optional[ListNode], cur: Optional[ListNode],n: int):
    if cur is not None:
        self.remove(cur,cur.next,n)

    if Solution.count == n:
        pre.next = cur.next
        Solution.count += 1

快慢指针

参考答案：快指针比慢指针先走n步

def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
    if head.next is None:
        return None
    hv = ListNode(next=head)
    slow,fast = hv,hv
    while n != 0:
        fast = fast.next
        n -= 1
    while fast.next is not None:
        slow = slow.next
        fast = fast.next
    slow.next = slow.next.next
    return hv.next

6.链表相交

自己答案：链表A和B的长度分别为lenA和lenB，假设 lenA > lenB，先遍历A比B长的部分，即lenA-lenB的长度，之后遍历A和B依次比较结点是否相等(相交必有节点相等)

def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
    lenA,lenB = 0,0
    curA,curB = headA,headB
    while curA is not None:
        lenA += 1
        curA = curA.next

    while curB is not None:
        lenB += 1
        curB = curB.next

    curA, curB = headA, headB
    if lenA > lenB:
        cnt = lenA - lenB
        while cnt > 0:
            curA = curA.next
            cnt -= 1
    else:
        cnt = lenB - lenA
        while cnt > 0:
            curB = curB.next
            cnt -= 1
    while curA is not None:
        if curA == curB:
            return curA
        curA = curA.next
        curB = curB.next
    return None

7.环形链表 II(2)

使用set缓存

每次遍历把节点放入，如果发现此节点在set中存在的，说明是环形链表

空间复杂度o(n)，时间复杂度o(n)

public ListNode detectCycle(ListNode head) {
    Set<ListNode> visited = new HashSet<>();
    ListNode cur = head;
    while (cur!=null){
        if (visited.contains(cur)){
            return cur;
        }else {
            visited.add(cur);
        }
        cur = cur.next;
    }
    return null;
}

使用O(1)的空间

快慢指针

几个问题：

1.如果存在环形链表快指针一定会追上慢指针 √ 判断链表是否有环

? 快指针每次都以一个节点的速度靠近慢指针

2.为什么遍历cur和slow，cur和slow会有相等的时候，明明步数都是1

2.1 快指针追上慢指针的时候 慢指针一定没有走完一圈

? 假设环长度为n，若快指针在0.1n的位置，慢指针走一圈环(1步)，快指针(2步)一定已经绕一圈且追上了慢指针

def detectCycle(self, head: ListNode) -> ListNode:
    slow,fast = head,head
    while fast is not None:
        if fast.next is not None:
            fast = fast.next.next
        else:
            return None
        slow = slow.next
        if fast == slow:
            cur = head
            while cur != slow:
                cur = cur.next
                slow = slow.next
            return cur
    return None

总结