单链表解题思维

  

• 确定解题的链表类型  
  
• 画图理清思路  
  
• 确定边界条件
  

const head = {
  data: 1,
  next: {
  data: 2,
  next: null,
  },
};

示例:
  输入: l1 = [1,2,4], l2 = [1,3,4]
  输出: [1,1,2,3,4,4]

  

• 解题的链表类型是单链表  
  
• 思路：
  
     
  
  • l1 与 l2 是有序递增的，因此 l1.val 与 l2.val 的较小值就是合并后链表的最小值   
    
  • 依次递归 大小节点的比较，直到 l1 l2 均为 null   
    
     
  
• 边界条件：递归到任意链表为 null 即可停止，并将 next 指向另外的链表
  

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

示例：
  输入：head = [3,2,0,-4], pos = 1 
  输出：true  // 链表中有一个环，其尾部连接到第二个节点

  

• 解题的链表类型是单链表  
  
• 思路：
  
     
  
  • 龟兔赛跑算法：利用快慢双指针，快指针走两步，慢指针走一步   
    
  • 如果链表存在环，则两个速度不同的指针必定会相遇。并且从相遇点和链表头结点同时往下走，会在环起点相遇   
    
     
  
• 边界条件：
  
     
  
  • 快指针指向 null 停止，无环   
    
  • 快慢指针指向同一个节点，有环   
    
    
  

var hasCycle = function(head) {
  if(!head || !head.next) return false;
  let slow = head.next;
  let fast = head.next.next;
  while(slow !== fast ) {
    if(!fast || !fast.next) return false;
    slow = slow.next;
    fast = fast.next.next;
  }
  return true
}

示例:
  输入: head = [1,2,3,4,5]
  输出: [5,4,3,2,1]

  

• 解题的链表类型是单链表  
  
• 迭代思路：
  
     
  
  • 将单链表的每个节点的后继指针指向它的前驱节点   
    
    
  

  

• 边界条件：
  
     
  
  • 当链表 null 停止   
    
  • 链表仅有一个节点   
    
    
  

var reverseList = function(head) {
  if(!head || !head.next) return head;
  let prev = null;
  let cur = head;
  while(cur) {
    const curNext = cur.next;
    // 反转后赋值给prev指针
    cur.next = prev;
    prev = cur;
    // 链接到下一个节点
    cur = curNext;
  }
  return prev
};

示例:
  输入: [1,2,3,4,5]
  输出:  3
  输入: [1,2,3,4,5,6]
  输出:  4

  

• 解题的链表类型是单链表  
  
• 思路：
  
     
  
  • 快指针p2的位移是慢指针p1的2倍，所以当p2走到链表尾部时，p1刚好走了一半，指向链表的中点。   
    
  • 下题同理   
    
    
  

  

• 边界条件：
  
     
  
  • 快指针指向 null 时，慢指针刚好处于中间位置   
    
    
  

var middleNode = function(head) {
  if(!head || !head.next) return head;
  let slow = head;
  let fast = head;
  while(fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow
};

示例：
  输入：head = [1,2,3,4,5], n = 2
  输出：[1,2,3,5]

  

• 解题的链表类型是单链表
    
  
• 思路：
  
     
  
  • 快指针一次性走完n个节点，接着两个指针一起往后走，直到快指针指向null，此时慢指针就是倒数第n个节点   
    
  • 添加哨兵处理第n个节点   
    
     
  
• 边界条件：
  
     
  
  • 快指针指向 null 时，慢指针所在位置就是倒数第n个节点   
    
    
  

const removeNthFromEnd = function (head, n) {
  // 哨兵
  let preHead = new ListNode(0)
  preHead.next = head
  let slow = preHead;
  let fast = preHead;
  // 先走n步
  while (n--) {
  fast = fast.next
  }
  // 一起走
  while (fast && fast.next) {
  fast = fast.next
  slow = slow.next
  }
  slow.next = slow.next.next
  return preHead.next;
};

示例:
  输入: head = [1,2,2,1]
  输出: true

  

• 解题的链表类型是单链表
    
  
• 思路：
  
     
  
  • 借助数组，将链表丢进数组   
    
  • 设置前后指针，前后指针理应相同，若不同则不是回文   
    
  • 循环结束若没有返回false则是回文   
    
     
  
• 边界条件：
  
     
  
  • 前后指针不一致   
    
  • 循环结束   
    
    
  

var isPalindrome = function (head) {
  const res = []
  while (head) {
  res.push(head.val);
  head = head.next
  }
  let pre = 0;
  let last = res.length - 1;
  while (pre < last) {
  if (res[pre] !== res[last]) return false;
  pre++;
  last--;
  }
  return true
}

  

• 函数返回结果后，链表必须 保持其原始结构(需复制新的链表)  
  
• 如果两个链表没有交点，返回 null  
  
• 程序尽量满⾜ O(n) 时间复杂度，且仅⽤ O(1) 内存
  

示例:
  输入：intersectVal = 4, listA = [1,2,3,4,5], listB = [6,7,4,5], skipA = 3, skipB = 2   // 在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 2 个节点
  输出：Intersected at '4'  // 相交节点的值为 4 （注意，如果两个链表相交则不能为 0）

  

• 解题的链表类型是单链表  
  
• 思路：
  
     
  
  • 同上，寻找AB链表的高度差并消除，已知相交点之后的长度必须相等   
    
  • AB双指针同时前进，当短链表B的指针遍历完成时，双指针的长度差刚好是双链表的长度差，将B指针指向A链表的头节点，跟着A指针再一次遍历，直到A指针遍历完成   
    
  • 同样将A指针指向B链表的头节点，B指针向前一步，则消除了链表的高度差   
    
    
  

  

• 边界条件：
  
     
  
  • 指针指向null时，切换指向链表   
    
  • AB链表值相等   
    
    
  

var getIntersectionNode = function (headA, headB) {
  if (!headA || !headB) return null;
  let pA = headA;
  let pB = headB;
  while (pA !== pB) {
  pA = pA !== null ? pA.next : headB;
  pB = pB !== null ? pB.next : headA;
  }
  return pA;
}

示例：
  输⼊：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
  输出：2 -> 1 -> 9，即912

  

• 解题的链表类型是单链表
    
  
• 思路：
  
     
  
  • 输出的是新链表，因此需要创建一个链表   
    
  • 由于是反向存储，则链表从个位数开始计算，大于十则进位   
    
  • 进位，首先考虑⽤carry存储每次的进位，余数存储进创建的节点   
    
     
  
• 边界条件：
  
     
  
  • 双链表指向null时，遍历完成   
    
  • 遍历完成，carry不为0，则还需前进一位   
    
    
  

const addTwoNumbers = function (l1, l2) {
  // 哨兵
  let preHead = new ListNode(0)
  let carry = 0;
  let pre = preHead;
  while (l1 || l2) {
  let sum = 0;
  if (l1) {
    sum += l1.val
    l1 = l1.next
  }
  if (l2) {
    sum += l2.val
    l2 = l2.next
  }
  sum += carry
  carry = Math.floor(sum / 10)
  pre.next = new ListNode(sum % 10)
  pre = pre.next
  }
  if (carry > 0) {
  pre.next = new ListNode(carry)
  pre = pre.next
  }
  return preHead.next
}

进阶：思考⼀下，假设这些数位是正向存放的，⼜该如何解决呢?
  输⼊：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
  输出：9 -> 1 -> 2，即912