链表

合并两个有序链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

  1. 输入：1->2->4, 1->3->4
  2. 输出：1->1->2->3->4->
  3. 限制：0 <= 链表长度 <= 1000
  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) { val = x; }
  7.  * }
  8.  */
  9. class Solution {
  10.     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
  11.         ListNode res = new ListNode(0); // 最终结果链表
  12.         ListNode cur = res; // 用于链表合并
  13.         while (l1 != null && l2 != null) {  // 这里循环最终会剩一个结果，l1或者l2
  14.             if (l1.val <= l2.val) {
  15.                 cur.next = l1;
  16.                 l1 = l1.next;
  17.             }else {
  18.                 cur.next = l2;
  19.                 l2 = l2.next;
  20.             }
  21.             cur = cur.next;
  22.         }
  23.         cur.next = l1 != null ? l1 : l2;    // 如果剩下是l1，则返回l1，如果l1为空，则剩下的是l2，返回l2
  24.         return res.next;    // 为什么不是res呢？因为实例化的时候定义了一个初始值为0
  25.     }
  26. }

判断链表中是否有环

  1. 哈希法：HashSet
  2. 快慢双指针

链表 - 图1