1 Reverse Linked List
public ListNode reverse(ListNode head) { // write your code here ListNode pre = null; while (head != null) { ListNode temp = head.next; head.next = pre; pre = head; head = temp; } return pre; } 2 Reverse Linked List II
public ListNode reverseBetween(ListNode head, int m , int n) { if (head == null || m >= n) { return head; } ListNode dummy = new ListNode(0); dummy.next = head; head = dummy; for (int i = 1; i < m; i++) { if (head == null) { return null; } head = head.next; } ListNode premNode = head; ListNode mNode = head.next; ListNode nNode = mNode; ListNode postnNode = mNode.next; for (int i = m; i < n; i++) { if(postnNode == null) { return null; } ListNode temp = postnNode.next; postnNode.next = nNode; nNode = postnNode; postnNode = temp; } mNode.next = postnNode; premNode.next = nNode; return dummy.next; } 不熟悉
3 Remove Duplicates from Sorted List
public static ListNode deleteDuplicates(ListNode head) { if (head == null) { return head; } ListNode node = head; while (node != null) { if (node.next != null && node.val == node.next.val) { node.next = node.next.next; } else { node = node.next; } } return head; } 不熟悉
4 Remove Duplicates from Sorted List II
public static ListNode deleteDuplicates(ListNode head) { // write your code here if (head == null || head.next == null) { return head; } ListNode dummy = new ListNode(0); dummy.next = head; head = dummy; while (head.next != null && head.next.next != null) { if (head.next.val == head.next.next.val) { int val = head.next.val; while (head.next != null && head.next.val == val) { head.next = head.next.next; } } else { head = head.next; } } return dummy.next; } don't care
5 Partition List
public ListNode partition(ListNode head, int x) { // write your code here if (head == null) { return head; } ListNode leftDummy = new ListNode(0); ListNode rightDummy = new ListNode(0); ListNode left = leftDummy; ListNode right = rightDummy; while (head != null) { if (head.val < x) { left.next = head; left = head; } else { right.next = head; right = head; } head = head.next; } left.next = rightDummy.next; right.next = null; return leftDummy.next; } 6 Merge Two Sorted Lists
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode tail = dummy; while (l1 != null && l2 != null) { if (l1.val < l2.val) { tail.next = l1; l1 = l1.next; } else { tail.next = l2; l2 = l2.next; } tail = tail.next; } if (l1 != null) { tail.next = l1; } else { tail.next = l2; } return dummy.next; } 7 Sort List
public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode slow = findMiddle(head); ListNode left = sortList(slow.next); slow.next = null; ListNode right = sortList(head); return mergeTwoLists(left, right); } ListNode findMiddle(ListNode head) { ListNode slow = head; ListNode fast = head.next; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow; } return slow; } ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode tail = dummy; while (l1 != null && l2 != null) { if (l1.val < l2.val) { tail.next = l1; l1 = l1.next; } else { tail.next = l2; l2 = l2.next; } tail = tail.next; } if (l1 != null) { tail.next = l1; } else { tail.next = l2; } return dummy.next; } public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode slow = findMiddle(head); ListNode left = sortList(slow.next); slow.next = null; ListNode right = sortList(head); return mergeTwoLists(left, right); } ListNode findMiddle(ListNode head) { ListNode slow = head; ListNode fast = head.next; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } return slow; } ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode tail = dummy; while (l1 != null && l2 != null) { if (l1.val < l2.val) { tail.next = l1; l1 = l1.next; } else { tail.next = l2; l2 = l2.next; } tail = tail.next; } if (l1 != null) { tail.next = l1; } else { tail.next = l2; } return dummy.next; } 8 Reorder List
public void reorderList(ListNode head) { if (head == null || head.next == null) { return; } ListNode mid = findMiddle(head); ListNode tail = reverse(mid.next); mid.next = null; merge(head, tail); } ListNode findMiddle(ListNode head) { ListNode slow = head; ListNode fast = head.next; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } return slow; } ListNode reverse(ListNode head) { // write your code here ListNode pre = null; while (head != null) { ListNode temp = head.next; head.next = pre; pre = head; head = temp; } return pre; } void merge(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode tail = dummy; int index = 0; while (l1 != null && l2 != null) { if (index % 2 == 0) { tail.next = l1; l1 = l1.next; } else { tail.next = l2; l2 = l2.next; } tail = tail.next; index++; } if (l1 != null) { tail.next = l1; } else { tail.next = l2; } } 9 Remove Nth Node From End of List
ListNode removeNthFromEnd(ListNode head, int n) { if (n <= 0) { return head; } ListNode dummy = new ListNode(0); dummy.next = head; ListNode preDelete = dummy; for(int i = 0; i < n; i++) { if (head == null) { return null; } head = head.next; } while (head != null) { preDelete = preDelete.next; head = head.next; } preDelete.next = preDelete.next.next; return dummy.next; } 10 Linked List Cycle
public boolean hasCycle(ListNode head) { if (head == null) { return false; } ListNode fast = head.next; ListNode slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { return true; } } return false; } 11 Linked List Cycle II
public ListNode detectCycle(ListNode head) { ListNode slow = head; ListNode fast = head; boolean hasCycle = false; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { hasCycle = true; break; } } if (!hasCycle) { return null; } fast = head; while (fast != slow) { fast = fast.next; slow = slow.next; } return fast; } 12 Merge k Sorted Lists
private ComparatorListNodeComparator = new Comparator () { public int compare(ListNode left, ListNode right) { return left.val - right.val; } }; public ListNode mergeKLists(List lists) { if (lists == null || lists.size() == 0) { return null; } Queue heap = new PriorityQueue (lists.size(), ListNodeComparator); for (int i = 0; i < lists.size(); i++) { if (lists.get(i) != null) { heap.add(lists.get(i)); } } ListNode dummy = new ListNode(0); ListNode tail = dummy; while (!heap.isEmpty()) { ListNode node = heap.poll(); tail.next = node; tail = node; if (node.next != null) { heap.add(node.next); } } return dummy.next; }
13 Convert Sorted List to Balanced BST
public TreeNode sortedListToBST(ListNode head) { // write your code here if (head == null) { return null; } int count = 0; ListNode cur = head; while (cur != null) { cur = cur.next; count++; } ArrayList list = new ArrayList (); list.add(head); return helper(list, 0, count - 1); } public TreeNode helper(ArrayList list, int l, int r) { if (l > r) { return null; } int m = (l + r) / 2; TreeNode left = helper(list, l, m - 1); TreeNode root = new TreeNode(list.get(0).val); root.left = left; list.set(0, list.get(0).next); root.right = helper(list, m + 1, r); return root; }