合并链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。
示例： 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
思路：比较当前两个元素大小，小的添入链表。循环进行，直至链表为空
注意⚠️：处理链表的本质，是处理链表结点之间的指针关系。

  1. /**
  2.  * @param {ListNode} l1
  3.  * @param {ListNode} l2
  4.  * @return {ListNode}
  5.  */
  6. const mergeTwoLists = function(l1, l2) {
  7.   // 定义头结点，确保链表可以被访问到
  8.   let head = new ListNode()
  9.   // cur 这里就是咱们那根“针”
  10.   let cur = head
  11.   // “针”开始在 l1 和 l2 间穿梭了
  12.   while(l1 && l2) {
  13.       // 如果 l1 的结点值较小
  14.       if(l1.val<=l2.val) {
  15.           // 先串起 l1 的结点
  16.           cur.next = l1
  17.           // l1 指针向前一步
  18.           l1 = l1.next
  19.       } else {
  20.           // l2 较小时，串起 l2 结点
  21.           cur.next = l2
  22.           // l2 向前一步
  23.           l2 = l2.next
  24.       }
  26.       // “针”在串起一个结点后，也会往前一步
  27.       cur = cur.next 
  29.   }
  31.   // 处理链表不等长的情况
  32.   cur.next = l1!==null?l1:l2
  33.   // 返回起始结点
  34.   return head.next
  35. };

链表节点的删除

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

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

示例 2:

输入: 1->1->2->3->3

输出: 1->2->3

注意⚠️：链表的遍历用while

  1. /**
  2.  * @param {ListNode} head
  3.  * @return {ListNode}
  4.  */
  5. const deleteDuplicates = function(head) {
  6.     // 设定 cur 指针，初始位置为链表第一个结点
  7.     let cur = head;
  8.     // 遍历链表
  9.     while(cur != null && cur.next != null) {
  10.         // 若当前结点和它后面一个结点值相等（重复）
  11.         if(cur.val === cur.next.val) {
  12.             // 删除靠后的那个结点（去重）
  13.             cur.next = cur.next.next;
  14.         } else {
  15.             // 若不重复，继续遍历
  16.             cur = cur.next;
  17.         }
  18.     }
  19.     return head;
  20. };

链表反转

  1. function reverse(nodeLst){
  2.     var pNode = nodeLst; 
  3.     var pPre = null;   //翻转之后 第一个节点的next值 为 null   
  4.     var pNext;
  5.     while(pNode) {
  6.         pNext = pNode.next;        //获取到当前节点的下一个节点
  7.         pNode.next = pPre;         //当前节点的前一个指向上一个节点
  8.         pPre = pNode;               //上一个节点赋值为当前节点
  9.         pNode = pNext;              //当前节点赋值为下一个节点
  10.     }
  11.     return pPre;
  12. }

图解链接：https://zhuanlan.zhihu.com/p/102908327