Convert Binary Search Tree to Doubly Linked List

rwang23 · Jan 18, 2016 · 0de9c70 · 0de9c70
1 parent a44bf0e
commit 0de9c70
Show file tree

Hide file tree

Showing 4 changed files with 198 additions and 35 deletions.
diff --git a/Linkedlist/Convert-Binary-Search-Tree-to-Doubly-Linked-List.md b/Linkedlist/Convert-Binary-Search-Tree-to-Doubly-Linked-List.md
@@ -0,0 +1,73 @@
+##Convert Binary Search Tree to Doubly Linked List
+
+	Convert a binary search tree to doubly linked list with in-order traversal.
+
+	Example
+	Given a binary search tree:
+
+	    4
+	   / \
+	  2   5
+	 / \
+	1   3
+	return 1<->2<->3<->4<->5
+
+####Tags Expand
+Linked List
+
+
+####解法
+- 简单的中序遍历
+- 一遍遍历,一遍就输出双向链表
+- 用非递归也是一样
+
+```java
+/**
+ * Definition of TreeNode:
+ * public class TreeNode {
+ *     public int val;
+ *     public TreeNode left, right;
+ *     public TreeNode(int val) {
+ *         this.val = val;
+ *         this.left = this.right = null;
+ *     }
+ * }
+ * Definition for Doubly-ListNode.
+ * public class DoublyListNode {
+ *     int val;
+ *     DoublyListNode next, prev;
+ *     DoublyListNode(int val) {
+ *         this.val = val;
+ *         this.next = this.prev = null;
+ *     }
+ * }
+ */
+public class Solution {
+    /**
+     * @param root: The root of tree
+     * @return: the head of doubly list node
+     */
+    DoublyListNode cur = new DoublyListNode(0);
+    DoublyListNode dummy = cur;
+    DoublyListNode pre = null;
+
+    public DoublyListNode bstToDoublyList(TreeNode root) {
+        // Write your code here
+        if (root == null) {
+            return null;
+        }
+
+        bstToDoublyList(root.left);
+
+        cur.next =  new DoublyListNode(root.val);
+        pre = cur;
+        cur = cur.next;
+        cur.prev = pre;
+
+        bstToDoublyList(root.right);
+
+        return dummy.next;
+    }
+}
+
+```
diff --git a/Linkedlist/Reorder-List.md b/Linkedlist/Reorder-List.md
@@ -15,7 +15,7 @@
 
 ####思路
 - 拆分，然后后半段翻转，再merge
-- 重做
+- 重做 : 完成
 
 ```java
 /**
@@ -39,51 +39,49 @@ public class Solution {
         if (head == null || head.next == null) {
             return;
         }
-        ListNode slow = head;
+
+        ListNode dummy = new ListNode(0);
+        dummy.next = head;
         ListNode fast = head;
-        while (fast != null && fast.next != null) {
+        ListNode slow = head;
+
+        while (fast.next != null && fast.next.next != null) {
             fast = fast.next.next;
             slow = slow.next;
         }
-        ListNode tail = reverse(slow.next);
+
+        ListNode half = slow.next;
         slow.next = null;
+        half = reverseList(half);
 
-        int index = 0;
-        ListNode dummy = new ListNode(0);
-        ListNode temp = dummy;
-        while (head!=null && tail != null) {
-            if (index % 2 == 0) {
-                dummy.next = head;
-                head = head.next;
-            } else {
-                dummy.next = tail;
-                tail = tail.next;
-            }
-            dummy = dummy.next;
-            index ++;
+        while (head != null && half != null) {
+            ListNode next = head.next;
+            ListNode secondnext = null;
+            secondnext = half.next;
+            head.next = half;
+            half.next = next;
+            head = next;
+            half = secondnext;
         }
-         if (head != null) {
-            dummy.next = head;
-        } else {
-            dummy.next = tail;
-        }
-        head = temp.next;
+
     }
 
-    public ListNode reverse(ListNode head) {
-        // write your code here
-        if (head == null ) {
-            return null;
+    public ListNode reverseList(ListNode head) {
+        if (head == null || head.next == null) {
+            return head;
         }
-        ListNode cur = head;
-        ListNode reverse = null;
-        while (cur != null) {
-            ListNode temp = cur.next;
-            cur.next = reverse;
-            reverse = cur;
-            cur = temp;
+
+        //ListNode dummy = new ListNode(0);
+        ListNode pre = null;
+
+        while (head != null) {
+            ListNode next = head.next;
+            head.next = pre;
+            pre = head;
+            head = next;
         }
-        return reverse;
+
+        return pre;
     }
 }
 

diff --git a/Linkedlist/Sort-List.md b/Linkedlist/Sort-List.md
@@ -83,6 +83,96 @@ public class Solution {
 
     }
 }
+```
 
+####Merge Sort的模板做法
+```java
+/**
+ * Definition for ListNode.
+ * public class ListNode {
+ *     int val;
+ *     ListNode next;
+ *     ListNode(int val) {
+ *         this.val = val;
+ *         this.next = null;
+ *     }
+ * }
+ */
+public class Solution {
+    /**
+     * @param head: The head of linked list.
+     * @return: You should return the head of the sorted linked list,
+     *             using constant space complexity.
+     */
+    public ListNode sortList(ListNode head) {
+        // write your code here
+        if (head == null || head.next == null) {
+            return head;
+        }
+
+        ListNode mid = findMiddle(head);
+        ListNode next = mid.next;
+        mid.next = null;
+
+        return helper(head, next);
+    }
+
+    public ListNode helper(ListNode headA, ListNode headB) {
+        if (headB == null) {
+            return headA;
+        }
+
+        ListNode mid = findMiddle(headA);
+        ListNode next = mid.next;
+        mid.next = null;
+        ListNode left = helper(headA, next);
+
+        mid = findMiddle(headB);
+        next = mid.next;
+        mid.next = null;
+        ListNode right = helper(headB, next);
+
+        return mergeTwoLists(left, right);
+    }
+
+    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
+        // write your code here
+        ListNode mergelist = new ListNode(0);
+        ListNode head = mergelist;
+        while (true) {
+            if (l1 == null) {
+                mergelist.next = l2;
+                break;
+            } else if (l2 == null) {
+                mergelist.next = l1;
+                break;
+            }
+            if (l1.val >= l2.val) {
+                mergelist.next = l2;
+                l2 = l2.next;
+            } else {
+                mergelist.next = l1;
+                l1 = l1.next;
+            }
+            mergelist = mergelist.next;
+        }
+        return head.next;
+    }
+
+    public ListNode findMiddle(ListNode head) {
+        if (head == null || head.next == null) {
+            return head;
+        }
+
+        ListNode fast = head;
+        ListNode slow = head;
+
+        while (fast.next != null && fast.next.next != null) {
+            fast = fast.next.next;
+            slow = slow.next;
+        }
+        return slow;
+    }
+}
 
 ```
diff --git a/SUMMARY.md b/SUMMARY.md
@@ -149,6 +149,8 @@ This is the summary of my experience in LintCode.
 	* [Reorder List](Linkedlist/Reorder-List.md)
 	* [Copy List With Random Pointer](Linkedlist/Copy-List-with-Random-Pointer.md)
 	* [Convert Sorted List to Binary Search Tree](Linkedlist/Convert-Sorted-List-to-Binary-Search-Tree.md)
+	* [Convert Binary Search Tree to Doubly Linked List](Linkedlist/Convert-Binary-Search-Tree-to-Doubly-Linked-List.md)
+
 
 * [Data Structure](DataStructure/README.md)
    * [String](DataStructure/string.md)