翻转列表

  1.     public ListNode reverseList(ListNode head) {
  2.         ListNode prev = null;
  3.         while (head != null) {
  4.             ListNode next = head.next;
  5.             head.next = prev;
  6.             prev = head;
  7.             head = next;
  8.         }
  9.         return prev;
  10.     }

链表归并排序

  1. class Solution {
  2.     public ListNode sortList(ListNode head) {
  3.         return sortList(head,null);
  4.     }
  6.     public ListNode sortList(ListNode head, ListNode tail) {
  7.         if (head == null) {
  8.             return head;
  9.         }
  10.         if (head.next == tail) {
  11.             head.next = null;
  12.             return head;
  13.         }
  14.         ListNode slow = head, fast = head;
  15.         while (fast != tail) {
  16.             slow = slow.next;
  17.             fast = fast.next;
  18.             if (fast != tail) {
  19.                 fast = fast.next;
  20.             }
  21.         }
  22.         ListNode mid = slow;
  23.         ListNode list1 = sortList(head, mid);
  24.         ListNode list2 = sortList(mid, tail);
  25.         ListNode sorted = merge(list1, list2);
  26.         return sorted;
  27.     }
  29.     public ListNode merge(ListNode head1, ListNode head2) {
  30.         ListNode dummyHead = new ListNode(0);
  31.         ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
  32.         while (temp1 != null && temp2 != null) {
  33.             if (temp1.val <= temp2.val) {
  34.                 temp.next = temp1;
  35.                 temp1 = temp1.next;
  36.             } else {
  37.                 temp.next = temp2;
  38.                 temp2 = temp2.next;
  39.             }
  40.             temp = temp.next;
  41.         }
  42.         if (temp1 != null) {
  43.             temp.next = temp1;
  44.         } else if (temp2 != null) {
  45.             temp.next = temp2;
  46.         }
  47.         return dummyHead.next;
  48.     }
  49. }