SOURCE

class ListNode {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}
let node1 = new ListNode(1);
let node2 = new ListNode(2);
let node3 = new ListNode(3);
let node4 = new ListNode(4);
let node5 = new ListNode(5);

node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;


/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
const mergeTwoLists = function(l1, l2) {
  // 定义头结点，确保链表可以被访问到
  let head = new ListNode()
  // cur 这里就是咱们那根“针”
  let cur = head
  // “针”开始在 l1 和 l2 间穿梭了
  while(l1 && l2) {
      // 如果 l1 的结点值较小
      if(l1.val<=l2.val) {
          // 先串起 l1 的结点
          cur.next = l1
          // l1 指针向前一步
          l1 = l1.next
      } else {
          // l2 较小时，串起 l2 结点
          cur.next = l2
          // l2 向前一步
          l2 = l2.next
      }
      
      // “针”在串起一个结点后，也会往前一步
      cur = cur.next 

  }
  
  // 处理链表不等长的情况
  cur.next = l1!==null?l1:l2
  // 返回起始结点
  return head.next
};

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

const deleteDuplicates = (head) => {
    let cur = head;
    while (cur !== null && cur.next !== null) {
        if (cur.val === cur.next.val) {
            // 相同元素 删除后面那个
            cur.next = cur.next.next;
        } else {
            cur = cur.next;
        }
    }
    return head;
}

// deleteDuplicates(node1);

// 真题描述： 给定一个排序链表，删除所有重复的元素，使重复元素全部被删除，只会留下不重复元素
// 思路：设定一个dummy节点，使之指向链表头部

const deleteRepeat = (head) => {
    if (!head || !head.next) {
        return false;
    }
    const dummy = new ListNode();
    dummy.next = head;
    let cur = dummy;
    while (cur.next && cur.next.next) {
        if (cur.next.val === cur.next.next.val) {
            // 说明后2个元素相同,记下这个值，并且再看下后面是否还有相同的值
            let sameVal = cur.next.val;
            while (cur.next && cur.next.val === sameVal) {
                cur.next = cur.next.next;
            }
        } else {
            cur = cur.next
        }
    }
    return dummy.next;
};

deleteRepeat(node1);
// console.log('=====', node1);

// 真题描述： 给定一个链表，删除链表倒数的第n个结点，并且返回链表的头结点
/*
  思路一：  
    - 倒数第n个转换成倒数第m个：m = len - n + 1
    - len的数值由第一次遍历得知并保存起来，定义变量count，一个不为空的结点便 +1 
    - 得到m之后，进行第二次遍历，到m-1 的节点时，这时候可以进行删除操作。
  思路二（快慢指针法）：
    - 2个指针fast,slow 分别指向链表头部
    - fast指针先出发 至第n个节点，停下来。
    - 然后slow指针跟fast指针同时出发，直至fast指针到达最后一个结点。这时候show指针所达到结点就是倒数第n个指针的前一个结点。在这进行删除动作；
**/

const deleteIndex = (head, n) => {
    if (!head || !head.next) {
        return false;
    }
    const dummy = new ListNode();
    dummy.next = head;

    let fast = dummy;
    let slow = dummy;

    while(n !== 0) {
        fast = fast.next;
        n --;
    }

    while (fast.next) {
        fast = fast.next;
        slow = slow.next;
    }

    slow.next = slow.next.next;

    return dummy.next;
};

// deleteIndex(node1, 4);
// console.log('======', node1);


// 真题描述：反转链表

const reverseList = (head) => {
    let pre = null;
    let cur = head;
    while (cur !== null) {
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

reverseList(node1);
console.log('444', node1);