【数据结构】链表

概述

• 链表的基本概念
• 经典问题分析
  • 反转链表
  • K 个一组翻转链表
  • 合并两个有序链表
• 参考

基本概念

反转链表

• 原题链接：https://leetcode.cn/problems/reverse-linked-list/

• 解题思路

  • 直观法：假设链表为 1 -> 2 -> 3 -> null，则反转后将变为 3 -> 2 -> 1 -> null。
    • 在遍历链表时，将当前节点的 next 指针改为指向前一个节点。
    • 由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。
    • 在更改引用之前，还需要存储后一个节点。

• 代码转化

  var reverseList = function (head) {
    let pre = null;
    let cur = head;
    while (cur) {
      let next = cur.next;
      cur.next = pre;
      pre = cur;
      cur = next;
    }
    return pre;
  };
  

K 个一组翻转链表

• 原题链接：https://leetcode.cn/problems/reverse-nodes-in-k-group/

• 思路分析

• 代码转化

  var reverseKGroup = function (head, k) {
    const myReverse = (head, tail) => {
      let prev = tail.next;
      let p = head;
      while (prev !== tail) {
        const nex = p.next;
        p.next = prev;
        prev = p;
        p = nex;
      }
      return [tail, head];
    };
  
    const hair = new ListNode(0);
    hair.next = head;
    let pre = hair;
    while (head) {
      let tail = pre;
      for (let i = 0; i < k; ++i) {
        tail = tail.next;
        if (!tail) {
          return hair.next;
        }
      }
      const nex = tail.next;
      [head, tail] = myReverse(head, tail);
      pre.next = head;
      tail.next = nex;
      pre = tail;
      head = tail.next;
    }
  
    return hair.next;
  };
  

合并两个有序链表

• 原题链接：https://leetcode.cn/problems/merge-two-sorted-lists/

• 思路分析

  • 可以递归求解！！！

• 代码转化

  var mergeTwoLists = function (list1, list2) {
    if (list1 === null) {
      return list2;
    } else if (list2 === null) {
      return list1;
    } else if (list1.val < list2.val) {
      list1.next = mergeTwoLists(list1.next, list2);
      return list1;
    } else {
      list2.next = mergeTwoLists(list1, list2.next);
      return list2;
    }
  };
  

参考