链表反转

  1. 双指针法
  3. public ListNode ReversalOfLinkedList(ListNode head) {
  4.     ListNode cur = head;
  5.     ListNode pre = null;
  6.     while(cur != null) {
  7.         ListNode curNext = cur.next;
  8.         cur.next = pre;
  9.         pre = cur;
  10.         cur = curNext;
  11.     }
  12.     return pre;
  13. }

合并两个有序链表

递归

  1. ???
  3. public mergeTwoLists(ListNode list1, ListNode list2) {
  4.     if(list1 == null) {
  5.       return list2;
  6.     } else if(list2 == null) {
  7.         return list1;
  8.     } else if(list1.val < list2.val) {
  9.         list1.next = mergeTwoLists(list1.next, list2);
  10.          return list1;
  11.     } else {
  12.            list2.next = mergeTwoLists(list1, list2.next);
  13.          return list2;
  14.     }
  15. }
  17. 时间复杂度: O(n+m),其中 n 和 m 分别为两个链表的长度
  18. 空间复杂度: O(n+m),其中 n 和 m 分别为两个链表的长度。

迭代

  1. public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
  2.   ListNode newHead = new ListNode(-1);
  3.   ListNode curNode = newHead;
  4.   while(list1 != null && list2 != null) {
  5.     if(list1.val < list2.val) {
  6.       curNode.next = list1;
  7.       list1 = list1.next; 
  8.     } else {
  9.       curNode.next = list2;
  10.       list2 = list2.next;
  11.     }
  12.     curNode = curNode.next;
  13.   }
  14.   curNode.next = list1 == null ? list2 : list1;
  15.   return newHead.next;
  16. }
  17. 时间复杂度：O(n + m),其中 n 和 m 分别为两个链表的长度。
  18. 空间复杂度: O(1), 只需要常数的空间存放若干变量。

查找链表中间节点

  1. public ListNode findMidNode(ListNode head) {
  2.     if(head == null || head.next == null) {
  3.         return head;
  4.     }
  5.     ListNode fast = head;
  6.     ListNode slow = head;
  7.     while(fast.next != null && fast.next.next != null) {
  8.         fast = fast.next.next;
  9.         slow = slow.next;
  10.     }
  11.     return slow;
  12. }
  14. 当链表个数为偶数时：正好前后一样多，slow在前半部分的最后一个节点
  15. 当链表个数为奇数时：slow在中间位置，slow两边一样多

判断链表有环

判断链表有环，并且找到入口节点

  1. public ListNode detectCycle(ListNode head) 
  2.     if(head  == null || head.next == null) {
  3.     return null;
  4.     }
  6.     ListNode fast = head;
  7.     ListNode slow = head;
  9.     while(fast.next != null && fast.next.next != null) {
  10.         fast = fast.next.next;
  11.         slow = slow.next;
  12.         // 如果相遇了，则必定有环
  13.         if(slow == fast) {
  14.             slow = head;
  15.             while(slow != fast) {
  16.             slow = slow.next;
  17.             fast = fast.next;
  18.             }
  19.             return slow;
  20.         }
  21.     }
  22.     return null;
  23. }