一、题目：在单链表和双链表中删除倒数第K个节点
分别实现两个函数，一个可以删除单链表中倒数第K个节点，另一个可以删除双链表中倒数第K个节点。
要求：如果链表长度为N，时间复杂度达到O（N），额外空间复杂度达到O（1）
单链表思路：
遍历链表，每移动一步，K-1。如果链表结束，K>0 ，则不存在倒数第K个节点。如果 K == 0，则将链表的头节点删除。如果K<0，则遍历第二遍链表。
import copy class Node: def __init__(self,value): self.value = value self.next = None def delete(head,k): if k < 1 or not head: return head head1 = head while head1: head1 = head1.next k -= 1 if k > 0: return elif k == 0: head = head.next else: head1 = head k += 1 while k != 0: head1 = head1.next k += 1 head1.next = head1.next.next return head head = Node(1) head.next = Node(2) head.next.next = Node(3) head.next.next.next = Node(4) k = 2 delete(head,k)
双链表的思路：
和单链表一样，只是在删除链表节点的地方考虑双链表的 last 指向。
class Node: def __init__(self,value): self.value = value self.last = None self.next = None def delete(head,k): if k < 1 or not head: return head head1 = head while head1: head1 = head1.next k -= 1 if k > 0: return elif k == 0: head = head.next head.last = None else: head1 = head k += 1 while k != 0: head1 = head1.next k += 1 head1.next = head1.next.next if head1.next: head1.next.last = head1 return head head = Node(1) head.next = Node(2) head.last = None head.next.next = Node(3) head.next.last = head head.next.next.next = Node(4) head.next.next.last = head.next head.next.next.next.last = head.next.next k = 2 delete(head,k)
二、题目：删除链表中间节点或者特定位置的节点
删除中间节点的思路：
初始：如果链表为空或者长度为1，直接返回。如果链表的长度为2，则将头结点删除。
遍历链表，链表长度每增加2，要删除的节点就后移一个节点。
代码：
class Node: def __init__(self,value): self.value = value self.next = None def deleteMed(head): if not head or not head.next: return head if not head.next.next: return head.next pre = head cur = head.next.next while cur.next and cur.next.next: pre = pre.next cur = cur.next.next pre.next = pre.next.next return head head = Node(1) head.next = Node(2) head.next.next = Node(3) head.next.next.next = Node(4) deleteMed(head)
删除特定位置 a/b 的节点的思路：
确定链表长度n ,再 n * a/b 确定要删除节点的位置。
代码：
import math class Node: def __init__(self,value): self.value = value self.next = None def deleteMed(head,a,b): if not head or a < 1 or a>b: return head n = 0 pre = head while pre: pre = pre.next n += 1 m = math.ceil(n * a / b) if m == 1: head = head.next return head pre = head m -= 1 while m != 1: pre = pre.next m -= 1 pre.next = pre.next.next return head head = Node(1) head.next = Node(2) head.next.next = Node(3) head.next.next.next = Node(4) a = 2 b = 3 deleteMed(head,a,b)
三、题目：将单链表中重复的值删除
方法一：利用字典。时间复杂度O（N），空间复杂度O（N）
遍历链表，如果在字典中，则将当前节点删除，如果不在就下一个。
代码：
def removeList(head): if not head: return None dic = {head:1} cur = head.next pre = head while cur: if cur not in dic: dic[cur] = 1 pre = pre.next else: pre.next = cur.next cur = pre.next return head
方法二：类似选择排序，时间复杂度O（N2），空间复杂度O（1）
代码：
def removeList(head): if not head: return None cur = head while cur: pre = cur next = cur.next while next: if next.value == cur.value: pre.next = next.next else: pre = pre.next next = next.next cur = cur.next
五、题目：给定一个节点，但不知该链表的头节点，怎么删除该节点，时间复杂度O（1）
