leetcode21 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode() {}
  7.  *     ListNode(int val) { this.val = val; }
  8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  9.  * }
  10.  */
  12. // v1.0 循环
  13. class Solution {
  14.     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
  15.         ListNode dummyNode = new ListNode(0);
  16.         ListNode curr = dummyNode;
  17.         while(l1!=null&&l2!=null){
  18.             if(l1.val<l2.val){
  19.                 curr.next = l1;
  20.                 curr = curr.next;
  21.                 l1 = l1.next;
  22.             }else{
  23.                 curr.next = l2;
  24.                 curr = curr.next;
  25.                 l2 = l2.next;
  26.             }
  27.         }
  28.         if(l1 == null){
  29.             curr.next = l2;
  30.         }
  31.         if(l2 == null){
  32.             curr.next = l1;
  33.         }
  34.         return dummyNode.next;
  35.     }
  36. }
  38. // v2.0 递归
  39. class Solution {
  40.     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
  41.         if(l1==null) return l2;
  42.         if(l2==null) return l1;
  43.         ListNode res = l1.val<l2.val? l1:l2;
  44.         res.next = mergeTwoLists(res.next, l1.val >= l2.val? l1:l2);
  45.         return res;
  46.     }
  47. }

leetcode 203 移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。 

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode() {}
  7.  *     ListNode(int val) { this.val = val; }
  8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  9.  * }
  10.  */
  11. //v1.0 添加一个虚拟头节点
  12. class Solution {
  13.     public ListNode removeElements(ListNode head, int val) {
  14.         ListNode dummyNode = new ListNode(-1);
  15.         dummyNode.next = head;
  16.         ListNode curr = dummyNode;
  17.         while(curr.next!=null){
  18.             if(curr.next.val == val){
  19.                 curr.next = curr.next.next;
  20.             }else{
  21.                 curr = curr.next;
  22.             }
  23.         }
  24.         return dummyNode.next;
  25.     }
  26. }
  28. //v2.0 递归 ★（还未看懂）
  29. class Solution {
  30.     public ListNode removeElements(ListNode head, int val) {
  31.        if(head==null)
  32.            return null;
  33.         head.next=removeElements(head.next,val);
  34.         if(head.val==val){
  35.             return head.next;
  36.         }else{
  37.             return head;
  38.         }
  39.     }
  40. }

leetcode 206 反转链表

反转一个单链表。
示例:

  1. 输入: 1->2->3->4->5->NULL
  2. 输出: 5->4->3->2->1->NULL
  1. /*
  2.     方法1：迭代 时间复杂度O(n) 空间复杂度O(1)
  4. */
  5. class Solution {
  6.     public ListNode reverseList(ListNode head) {
  7.         ListNode prev = null;
  8.         ListNode curr = head;
  9.         while(curr!=null){
  10.             ListNode temp = curr.next;
  11.             curr.next = prev;
  12.             prev = curr;
  13.             curr = temp;
  14.         }
  15.         return prev;
  16.     }
  17. }

leetcode148 排序链表

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode() {}
  7.  *     ListNode(int val) { this.val = val; }
  8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  9.  * }
  10.  */
  11. public ListNode sortList(ListNode head) {
  12.         // 归并排序
  13.         return mergeSort(head);
  14.     }
  15.     public ListNode mergeSort(ListNode head){
  16.         // 如果结点为空或只有一个结点的话，没必要排序
  17.         if(head==null||head.next==null){
  18.             return head;
  19.         }
  20.         ListNode dummy = new ListNode(-1,head);
  21.         ListNode quick = head, slow = head;
  22.         while(quick!=null&&quick.next!=null){
  23.             dummy = dummy.next;
  24.             quick = quick.next.next;
  25.             slow = slow.next;
  26.         }
  27.         dummy.next = null;
  28.         ListNode left = mergeSort(head);
  29.         ListNode right = mergeSort(slow);
  30.         return merge(left,right);
  31.     }
  32.     public ListNode merge(ListNode left, ListNode right){
  33.         ListNode dummy = new ListNode(-1);
  34.         ListNode tmp = dummy;
  35.         while(left!=null&&right!=null){
  36.             if(left.val<right.val){
  37.                 tmp.next = left;
  38.                 left = left.next;
  39.             }else{
  40.                 tmp.next = right;
  41.                 right = right.next;
  42.             }
  43.             tmp = tmp.next;
  44.         }
  45.         if(left!=null){
  46.             tmp.next = left;
  47.         }
  48.         if(right!=null){
  49.             tmp.next = right;
  50.         }
  51.         return dummy.next;
  52.     }

leetcode234 回文链表

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode() {}
  7.  *     ListNode(int val) { this.val = val; }
  8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  9.  * }
  10.  */
  11. class Solution {
  12.     public boolean isPalindrome(ListNode head) {
  13.         //定义快慢指针
  14.         ListNode slow = head;
  15.         ListNode fast = head;
  16.         while(fast!=null&&fast.next!=null){
  17.             fast = fast.next.next;
  18.             slow = slow.next;
  19.         }
  20.         ListNode curr = slow;
  21.         if(fast!=null){
  22.             curr = slow.next; //curr用来反转后半链表，若为奇数链表，则后移一位
  23.         }
  24.         //反转链表
  25.         ListNode prev = null;
  26.         while(curr!=null){
  27.             ListNode temp = curr.next;
  28.             curr.next = prev;
  29.             prev = curr;
  30.             curr = temp;
  32.         }
  33.         //判断是否是回文链表
  34.         while(prev!=null){
  35.             if(prev.val==head.val){
  36.                 prev = prev.next;
  37.                 head = head.next;
  38.             }
  39.             else{
  40.                 return false;
  41.             }
  42.         }
  43.         return true;
  44.     }
  45. }

leetcode 160 相交链表

  1. public class Solution {
  2.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  3.         if(headA==null || headB==null){
  4.             return null;
  5.         }
  6.         ListNode leftNode = headA;
  7.         ListNode rightNode = headB;
  8.         while(leftNode!=rightNode){
  9.             leftNode = leftNode==null? headB:leftNode.next;
  10.             rightNode = rightNode==null? headA:rightNode.next;
  11.         }
  12.         return leftNode;
  15.     }
  16. }

leetcode 82 删除排序链表中的重复元素II

  1. class Solution {
  2.     public ListNode deleteDuplicates(ListNode head) {
  3.         if(head==null||head.next==null){
  4.             return head;
  5.         }
  7.         ListNode nextNode = head.next;
  8.         if(head.val==nextNode.val){
  9.             while(nextNode!=null&&head.val==nextNode.val){
  10.                 nextNode = nextNode.next;
  11.             }
  12.             head = deleteDuplicates(nextNode);
  13.         }else{
  14.             head.next = deleteDuplicates(nextNode);
  15.         }
  16.         return head;
  18.     }
  19. }

leetcode 2 两数相加

  1. class Solution {
  2.     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  3.         ListNode dummyOne = new ListNode(-1, l1);
  4.         ListNode dummyTwo = new ListNode(-1, l2);
  5.         ListNode dummy = new ListNode(-1);
  6.         ListNode curr = dummy;
  7.         ListNode currOne = dummyOne;
  8.         ListNode currTwo = dummyTwo;
  9.         int carry = 0;
  10.         int val = 0;
  11.         while(currOne.next!=null||currTwo.next!=null){
  12.             val = (currOne.next.val+currTwo.next.val+carry)%10;
  13.             carry = (currOne.next.val+currTwo.next.val+carry)/10;
  14.             curr.next = new ListNode(val);
  15.             curr = curr.next;
  16.             currOne = currOne.next;
  17.             currTwo = currTwo.next;
  18.             if(currOne.next==null&&currTwo.next==null){
  19.                 break;
  20.             }
  21.             if(currOne.next==null){
  22.                 currOne.next = new ListNode(0);
  23.             }
  24.             if(currTwo.next==null){
  25.                 currTwo.next = new ListNode(0);
  26.             }
  28.         }
  29.         if(carry>0){
  30.             curr.next = new ListNode(carry);
  31.         }
  32.         return dummy.next;
  33.     }
  34. }

leetcode 19 删除链表倒数第N个结点

  1. class Solution {
  2.     public ListNode removeNthFromEnd(ListNode head, int n) {
  3.         // 构建虚拟节点，因为可能删除首结点
  4.         ListNode dummy = new ListNode(-1,head);
  6.         ListNode low = dummy;
  7.         ListNode quick = dummy;
  8.         int count = 0;
  9.         if(head.next==null){
  10.             return null;
  11.         }
  12.         while(count!=n+1){
  13.             quick = quick.next;
  14.             count++;
  15.         }
  16.         while(quick!=null){
  17.             quick = quick.next;
  18.             low = low.next;
  19.         }
  20.         low.next = low.next.next;
  21.         return dummy.next;
  23.     }
  24. }

leetcode 23 合并K个升序链表

  1. //v1.0 暴力合并k个链表
  2. class Solution {
  3.     public ListNode mergeKLists(ListNode[] lists) {
  4.         ListNode dummy = new ListNode(-1);
  5.         ListNode tmp = dummy;
  6.         dfs(lists,tmp);
  7.         return dummy.next;
  8.     }
  9.     public void dfs(ListNode[] lists, ListNode node){
  10.         int index = -1;
  11.         int max = 100000;
  12.         for(int i=0;i<lists.length;i++){
  13.             if(lists[i]!=null){
  14.                 if(lists[i].val<max){
  15.                     index = i;
  16.                     max = lists[i].val;
  17.                 }
  18.             } 
  19.         }
  20.         if(index==-1){
  21.             return;
  22.         }else{
  23.             node.next = lists[index];
  24.             lists[index] = lists[index].next;
  25.             node = node.next;
  26.             dfs(lists, node);
  27.         }
  28.     }
  29. }
  31. // v2.0 分治算法
  32. class Solution {
  33.     public ListNode mergeKLists(ListNode[] lists) {
  34.         return merge(lists, 0, lists.length-1);
  36.     }
  37.     public ListNode merge(ListNode[] lists, int l, int r){
  38.         if(l==r){
  39.             return lists[l];
  40.         }
  41.         if(l>r){
  42.             return null;
  43.         }
  44.         int mid = (l+r)>>1;
  45.         return mergeTwoLists(merge(lists,l,mid), merge(lists,mid+1,r));
  46.     }
  47.     public ListNode mergeTwoLists(ListNode a, ListNode b){
  48.         ListNode dummy = new ListNode(-1);
  49.         ListNode tmp = dummy;
  50.         while(a!=null&&b!=null){
  51.             if(a.val>b.val){
  52.                 tmp.next = b;
  53.                 b = b.next;
  54.             }else{
  55.                 tmp.next = a;
  56.                 a = a.next;
  57.             }
  58.             tmp = tmp.next;
  59.         }
  60.         if(a!=null){
  61.             tmp.next = a;
  62.         }else{
  63.             tmp.next = b;
  64.         }
  65.         return dummy.next;
  67.     }
  68. }

leetcode 142 环形链表

  1. /**
  2.  * Definition for singly-linked list.
  3.  * class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) {
  7.  *         val = x;
  8.  *         next = null;
  9.  *     }
  10.  * }
  11.  */
  12. public class Solution {
  13.     public ListNode detectCycle(ListNode head) {
  14.         if(head==null){
  15.             return null;
  16.         }
  17.         ListNode qucik = head;
  18.         ListNode slow = head;
  19.         boolean hasCycle = false;
  20.         while(qucik.next!=null&&qucik.next.next!=null){
  21.             qucik=qucik.next.next;
  22.             slow = slow.next;
  23.             if(qucik == slow){
  24.                 hasCycle = true;
  25.                 break;
  26.             }
  27.         }
  28.         if(hasCycle){
  29.             ListNode tmp = head;
  30.             while(tmp!=slow){
  31.                 tmp = tmp.next;
  32.                 slow = slow.next;
  33.             }
  34.             return tmp;
  35.         }
  36.         return null;
  37.     }
  38. }