第三周：数组和链表

[azurepwq]

203. 移除链表元素（简单）

876. 链表的中间结点（简单）

83. 删除排序链表中的重复元素（简单）

剑指 Offer 25. 合并两个排序的链表（中等）

2. 两数相加（中等）

206. 反转链表（中等）

234. 回文链表（中等）

328. 奇偶链表（中等）

25. K 个一组翻转链表（困难）

剑指 Offer 22. 链表中倒数第k个节点（简单）

19. 删除链表的倒数第 N 个结点（中等）

160. 相交链表（简单）

141. 环形链表（简单）

[azurepwq]

203. 移除链表元素（简单）

/**
 * 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)
 *     }
 * }
 */

// Iterative
function removeElements(head: ListNode | null, val: number): ListNode | null {
  let dummyHead = new ListNode(null, head);
  let prev = dummyHead;

  while (prev.next !== null) {
    if (prev.next.val === val) {
      prev.next = prev.next.next
    } else {
      prev = prev.next;
    }
  } 

  return dummyHead.next;
};

/**
 * 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)
 *     }
 * }
 */

// Recursive
function removeElements(head: ListNode | null, val: number): ListNode | null {
  if (head === null) return null;

   head.next = removeElements(head.next, val);

  return head.val !== val ? head: head.next;
};

[azurepwq]

876. 链表的中间结点（简单）

/**
 * 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)
 *     }
 * }
 */

// Method 1
function middleNode(head: ListNode | null): ListNode | null {
  let p = head;
  let count = 0;
  while (p.next !== null) {
    p = p.next;
    count++;
  }

  let mid = Math.ceil(count / 2);
  while (mid-- > 0) head = head.next; 

  return 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)
 *     }
 * }
 */

// Method 2
function middleNode(head: ListNode | null): ListNode | null {
  let [slow, fast] = [head, head];

  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }

  return slow;
};

[azurepwq]

83. 删除排序链表中的重复元素（简单）

/**
 * 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)
 *     }
 * }
 */

// Iterative
function deleteDuplicates(head: ListNode | null): ListNode | null {
  const dummyHead = new ListNode(null); 
  let tail = dummyHead;

  while (head !== null) {
    if (tail.val !== head.val) {
      tail.next = head;
      tail = tail.next;
    }
    head = head.next;
  }

  tail.next = null;

  return dummyHead.next;
};

/**
 * 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)
 *     }
 * }
 */

// Recursive
function deleteDuplicates(head: ListNode | null): ListNode | null {
  if (head === null) return null;

  head.next = deleteDuplicates(head.next);

  return head.next?.val === head.val ? head.next: head;    
};

[azurepwq]

剑指 Offer 25. 合并两个排序的链表（中等）

/**
 * 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 trainningPlan(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  let p = new ListNode(null);
  const dummyHead = p;

  while (l1 && l2) {
    if (l1.val < l2.val) {
      p.next = l1;
      l1 = l1.next;      
    } else {
      p.next = l2;
      l2 = l2.next;
    }
    p = p.next;
  }

  if (l1) p.next = l1;
  if (l2) p.next = l2;

  return dummyHead.next;
};

[azurepwq]

2. 两数相加（中等）

/**
 * 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 addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  let p = new ListNode(null);
  const dummyHead = p;

  let carry = 0;
  while (l1 || l2) {
    const sum = (l1?.val ?? 0) + (l2?.val ?? 0) + carry;
    carry = sum > 9 ? 1 : 0;
    p.next = new ListNode(sum % 10);
    l1 && (l1 = l1.next);
    l2 && (l2 = l2.next);
    p = p.next;
  } 

  if (carry === 1) p.next = new ListNode(carry);

  return dummyHead.next;
};