反转链表

反转链表 (opens in a new tab)

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

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
 
function reverseList(head: ListNode | null): ListNode | null {
  let pre: ListNode = null;
  while (head) {
    const next = head.next;
    head.next = pre;
    pre = head;
    head = next;
  }
  return pre;
}

K 个一组翻转链表 (opens in a new tab)

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
 
function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
  if (!head) {
    return null;
  }
  let left, right;
  left = right = head;
  for (let i = 0; i < k; i++) {
    if (!right) {
      return head;
    }
    right = right.next;
  }
  const newHead = reverse(left, right);
  left.next = reverseKGroup(right, k);
  return newHead;
}
 
function reverse(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  let pre: ListNode = null;
  while (l1 !== l2) {
    const next = l1.next;
    l1.next = pre;
    pre = l1;
    l1 = next;
  }
  return pre;
}

Longest Substring Threesum