链表

链表倒置

leetcode 206 -easy 链表倒置

这题必须秒杀双指针, 同时记住反转链表这个模板题

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        pre = None
        while cur:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        return pre

leetcode 92 -mid 部分反转链表 去头去尾倒置中间部分

这道题在 反转 的前提下加入了反转范围, 难度还是有的, 值得多做几遍, 尤其需要注意各个部分的有效划分

class Solution:
    def reverseBetween(
        self, head: Optional[ListNode], left: int, right: int
    ) -> Optional[ListNode]:
        return_head = ListNode(next=head)
        number = right - left
        curr = return_head
        while left - 1 > 0:
            curr = curr.next
            left -= 1
        def reverse(head, number):
            count = 0
            pre = None
            curr = head
            temp_head = head
            while curr and count <= number:
                temp = curr.next
                curr.next = pre
                pre = curr
                curr = temp
                count += 1
            temp_head.next = curr
            return pre
        ptr = reverse(curr.next, number)
        curr.next = ptr
        return return_head.next

leetcode 445 mid 用链表模拟两数相加

这也说明你的 大数相加 还没有理解透彻,
可以做一个栈, 这样就不用倒序链表
还有优化的地方:

1. 原链表上修改
2. 逻辑判断

function addTwoNumbers(
  l1: ListNode | null,
  l2: ListNode | null
): ListNode | null {
  l1 = reverseLink(l1);
  l2 = reverseLink(l2);
  let carry = 0;
  let dummy = new ListNode(0);
  let curr = dummy;
  while (l1 || l2 || carry != 0) {
    let sum: number;
    if (l1 && l2) {
      sum = l1.val + l2.val + carry;
      if (sum >= 10) {
        carry = 1;
      } else {
        carry = 0;
      }
      l1 = l1.next;
      l2 = l2.next;
    } else if (l1) {
      sum = l1.val + carry;
      if (sum >= 10) {
        carry = 1;
      } else {
        carry = 0;
      }
      l1 = l1.next;
    } else if (l2) {
      sum = l2.val + carry;
      if (sum >= 10) {
        carry = 1;
      } else {
        carry = 0;
      }
      l2 = l2.next;
    } else if (carry != 0) {
      sum = carry;
      carry = 0;
    }
    let newNode = new ListNode(sum % 10);
    curr.next = newNode;
    curr = curr.next;
  }
  return reverseLink(dummy.next);
}
function reverseLink(head: ListNode) {
  let pre = null;
  let curr = head;
  while (curr) {
    let temp = curr.next;
    curr.next = pre;
    pre = curr;
    curr = temp;
  }
  return pre;
}

删除倒数第 N 个节点模板题

leetcode 61 -mid 旋转链表 (把链表平移 N 个单位, 注意拼接)

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        return_ptr = ListNode(next=head)
        end = return_ptr
        count = 0
        while end.next:
            end = end.next
            count += 1
        k = k % count if count != 0 else 0
        slow = return_ptr
        fast = return_ptr
        if k == 0:
            return head
        for i in range(k):
            fast = fast.next
        while fast.next:
            slow = slow.next
            fast = fast.next
        temp = slow.next
        slow.next = None
        fast.next = return_ptr.next
        return temp

链表删掉所有重复的节点 82 - mid (删除所有重复的节点)

这一题自己做了很久, 一直没想到 prev.next == curr: 这个判断条件来判断中间是否有元素改变,自己本来想的是声明一个变量来记录是否为重复元素, 结果没有做出来,同时这个 while():while() 循环自己也没有思考到, 这题是那种典型的一看就会一写就犯难, 值得多上手写几遍
感觉可以抽象出一个观点: 删除重复就用 whilewhile 循环

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        returnPtr = ListNode(next=head)
        prev = returnPtr
        curr = head
        while curr:
            while curr.next and curr.next.val == curr.val:
                curr = curr.next
            if prev.next == curr:
                prev = prev.next
            else:
                prev.next = curr.next
            curr = curr.next
        return returnPtr.next

引入 duplicate 其实也没有很麻烦,

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        returnPtr = ListNode(next=head)
        prev = returnPtr
        curr = head
        duplicate = False
        while curr:
            while curr.next and curr.next.val == curr.val:
                curr = curr.next
                duplicate = True
            if not duplicate:
                prev = prev.next
            else:
                prev.next = curr.next
                duplicate = False
            curr = curr.next
        return returnPtr.next

看起来蠢却是最直观的 方法, 时刻都要尊重第一想法

function deleteDuplicates(head: ListNode | null): ListNode | null {
  let dummy = new ListNode(0, head);
  let curr = dummy;
  while (curr.next && curr.next.next) {
    while (
      curr.next.val == curr.next.next.val &&
      curr.next.next.next &&
      curr.next.next.val == curr.next.next.next.val
    ) {
      curr.next.next.next = curr.next.next.next.next;
    }
    if (curr.next.val == curr.next.next.val) {
      curr.next = curr.next.next.next;
    } else {
      curr = curr.next;
    }
  }
  return dummy.next;
}

链表的遍历和条件构造

leetcode 86 mid 分隔列表 (把所有大于 x 的节点挑出来拼接)

这题的核心思路就是构造两条链表, 然后把他们拼起来,
这个思路不难, 但需要注意的是拼接后, 会有一段留尾, 需要单独把他们去除,
这里也凸显出来 dummy head 的重要性

class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        returnPtr = ListNode(next=head)
        sub_list = ListNode()
        sub_curr = sub_list
        curr = returnPtr
        while curr.next:
            if curr.next.val >= x:
                sub_curr.next = curr.next
                sub_curr = sub_curr.next
                curr.next = curr.next.next
            else:
                curr = curr.next
        if sub_curr.next and sub_curr.next.val < x:
            sub_curr.next = None
        curr.next = sub_list.next
        return returnPtr.next

leetcode 725 分隔链表 mid (给一个链表和一个整数 K,返回一个被分割为 k 个部分的链表)

class Solution:
    def splitListToParts(
        self, head: Optional[ListNode], k: int
    ) -> List[Optional[ListNode]]:
        length = self.link_length(head)
        array = self.arrary_number(length, k)
        print(array)
        return_list = []
        curr = head
        for i in range(k):
            dummy_node = ListNode(next=curr)
            if array[i] != 0:
                for j in range(array[i] - 1):
                    curr = curr.next
                temp = curr.next
                curr.next = None
                curr = temp
                return_list.append(dummy_node.next)
            else:
                return_list.append(None)
        return return_list
    def link_length(self, head):
        curr = head
        count = 0
        while curr:
            curr = curr.next
            count += 1
        return count
    def arrary_number(self, length, k):
        array = []
        if (length % k) == 0:
            for i in range(k):
                array.append(length // k)
        else:
            res = length % k
            for i in range(res):
                array.append(length // k + 1)
            for i in range(k - res):
                array.append(length // k)
        return array

leetcode 143 mid 重排链表 (S 型重排一个链表)

虽然做出来了, 但在前面找中点那里浪费了太多空间,
这样找中点会快很多

slow, fast = head, head.next 
while fast and fast.next: 
	slow = slow.next fast = fast.next.next

后续合并链表这样是不是更好些呢:

# Merge two halves 
first = head 
while second: 
	tmp1 = first.next 
	tmp2 = second.next 
	first.next = second 
	second.next = tmp1 
	first = tmp1 
	second = tmp2

我的解决方案:

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        dummy_node = ListNode(next=head)
        length = self.length_arr(head)
        lengthA, lengthB = self.lengthAB(length)
        curr = dummy_node
        for i in range(lengthA):
            curr = curr.next
        listB = curr.next
        curr.next = None
        listA = dummy_node.next
        listB = self.reverse(listB)
        pre = listA
        while listB:
            temp = pre.next
            pre.next = listB
            listB = listB.next
            pre.next.next = temp
            pre = pre.next.next
        return dummy_node.next
    def reverse(self, head):
        pre = None
        curr = head
        while curr:
            temp = curr.next
            curr.next = pre
            pre = curr
            curr = temp
        return pre
    def lengthAB(self, number):
        return (number + 1) // 2, number // 2
    def length_arr(self, head):
        count = 0
        curr = head
        while curr:
            curr = curr.next
            count += 1
        return count

ts 实现

function reorderList(head: ListNode | null): void {
  let dummy = new ListNode(0, head);
  let fast = dummy;
  let slow = dummy;
  while (fast && fast.next) {
    fast = fast.next.next;
    slow = slow.next;
  }
  let temp = slow.next;
  slow.next = null;
  let l2 = reverseList(temp);
  let l1 = dummy.next;
  while (l2) {
    let templ2 = l2.next;
    let temp = l1.next;
    l1.next = l2;
    l1.next.next = temp;
    l1 = temp;
    l2 = templ2;
  }
}
function reverseList(head) {
  let pre = null;
  let curr = head;
  while (curr) {
    let temp = curr.next;
    curr.next = pre;
    pre = curr;
    curr = temp;
  }
  return pre;
}

160. 相交链表 - 力扣（LeetCode）
题目描述：给你两个链表头，遍历两个链表，找到他们的第一个相交点（如果有的话）

• 方法一：遍历其中一个链表头，把所有的节点放到个数组里，在遍历第二个链表头，把若有重复的则返回
• 方法二：两个指针同时开始移动，一个头移动到末尾后就从另一个头开始继续运动，若两个指针指向了同一个节点，则说明找到了相交点。（核心就是两个都走了同样长的距离）
  注意：不要用 headA.next 来判定