链表练习题(学习笔记)

删除

1. 真题描述：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。

示例 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4

const a = {
  val: 1,
  next: {
    val: 2,
    next: {
      val: 4,
      next: null
    }
  }
}

const b = {
  val: 1,
  next: {
    val: 3,
    next: {
      val: 4,
      next: null
    }
  }
}

// 链表构造函数
function ListNode(val) {
  this.val = val || '';
  this.next = null
}

const mergeLists = function (list1, list2) {
  let head = new ListNode();
  let cur = head;

  // 只要有一个结束了就结束
  while (list1 && list2) {

    if (list1.val <= list2.val) {

      cur.next = list1;

      // list 向前一步
      list1 = list1.next;

    } else if (list1.val > list2.val) {

      cur.next = list2;
      // list 向前一步
      list2 = list2.next;
    }

    // 指针向前一步
    cur = cur.next;

  }
  // 不等长情况
  cur.next === list1 === null ? list2 : list1

  return head.next
}

// console.log(JSON.stringify(mergeLists(a, b)))

2.真题描述：给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:输入: 1->1->2->3->3 输出: 1->2->3

const c = {
  val: 1,
  next: {
    val: 1,
    next: {
      val: 2,
      next: {
        val: 3,
        next: {
          val: 3,
          next: null
        }
      }
    }
  }
}

const filterList = function (list) {
  let head = list; // 指针

  while (list.next) {
    if (list.val === list.next.val) {
      list.next = list.next.next;
      // 先前走一步
    } else {
      list = list.next;
    }
  }

  return head
}

// console.log(JSON.stringify(filterList(c)))

快慢指针——删除链表的倒数第 N 个结点

真题描述：给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

下方链表删除倒数第2个节点

const d = {
  val: 1,
  next: {
    val: 2,
    next: {
      val: 3,
      next: {
        val: 4,
        next: {
          val: 5,
          next: {
            val: 6,
            next: null
          }
        }
      }
    }
  }
}

const removeList = function (list, n) {

  let head = new ListNode;
  head.next = list

  let fast = head; // 快指针
  let slow = head; // 慢指针

  // 快指针先走
  while (n > 0) {
    fast = fast.next
    n--
  }

  // 开始走链表
  while (fast.next) {
    // 快慢指针同时走
    fast = fast.next;
    slow = slow.next;
  }

  // 此时慢指针就在倒数第N位上，删除该节点
  slow.next = slow.next.next

  return head.next

}

// console.log(JSON.stringify(removeList(d, 2)))

递归法—-链表的反转

真题描述：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

思路：翻转其实就是将next的指向翻转，后续节点的next指向前节点

const e = {
  val: 1,
  next: {
    val: 2,
    next: {
      val: 3,
      next: {
        val: 4,
        next: {
          val: 5,
          next: null
        }
      }
    }
  }
}


// 递归法
const reverseList = function (head, list) {

  if (list && head) {

    // 为了返回新链表，不改变原链表
    list = JSON.parse(JSON.stringify(list))

    // 缓存链表原本的next
    let cur = list.next;

    // 反向, 第一个节点next处理
    list.next = head.val ? head : null;

    return reverseList(list, cur)
  }

  return head
}

const head = new ListNode()

console.log(JSON.stringify(reverseList(head, e))) // {"val":5,"next":{"val":4,"next":{"val":3,"next":{"val":2,"next":{"val":1,"next":null}}}}}
console.log(JSON.stringify(e)) // {"val":1,"next":{"val":2,"next":{"val":3,"next":{"val":4,"next":{"val":5,"next":null}}}}}