添加单链表的相关算法

byhieg · byhieg · commit 8632db251c48 · 2017-05-02T21:27:12.000+08:00
diff --git a/src/main/java/cn/byhieg/algorithmtutorial/BinaryTree.java b/src/main/java/cn/byhieg/algorithmtutorial/BinaryTree.java
@@ -242,6 +242,32 @@ public static void mirror(Node root) {
         }
     }
 
+    /**
+     * 得到两个节点的最近公共祖先节点。
+     * 递归左右子树，如果返回的值都不为空，则表示在左右子树各找到一个target，因为最近的祖先就是cur
+     * 如果有一个为空，则就不为空就是最近公共祖先。
+     * @param root
+     * @param target1
+     * @param target2
+     * @return
+     */
+    public static Node findLCA(Node root, Node target1, Node target2) {
+        if (root == null)
+            return null;
+
+        if (root == target1 || root == target2) {
+            return root;
+        }
+        Node left = findLCA(root.left, target1, target2);
+        Node right = findLCA(root.right, target1, target2);
+        if (left != null && right != null) {
+            return root;
+        }
+        return left != null ? left:right;
+    }
+
+
+
     public static class Node {
         public int data;
         public Node left;
@@ -254,4 +280,6 @@ public Node(int data) {
             right = null;
         }
     }
+
+
 }
diff --git a/src/main/java/cn/byhieg/algorithmtutorial/SingleLinkList.java b/src/main/java/cn/byhieg/algorithmtutorial/SingleLinkList.java
@@ -0,0 +1,89 @@
+package cn.byhieg.algorithmtutorial;
+
+/**
+ * Created by byhieg on 17/5/2.
+ * Mail to byhieg@gmail.com
+ */
+public class SingleLinkList {
+
+
+    public Node head;
+
+    /**
+     * 在当前链表尾部插入一个节点
+     *
+     * @param data
+     * @return
+     */
+    public Node insertFromTail(int data) {
+        Node cur = getHead();
+        Node node = new Node(data);
+        if (cur == null) {
+            head = node;
+            return head;
+        } else {
+            while (cur.next != null) {
+                cur = cur.next;
+            }
+            cur.next = node;
+        }
+        return cur;
+    }
+
+    /**
+     * 在当前链表头部插入一个节点
+     *
+     * @param data
+     * @return
+     */
+    public Node insertFromHead(int data) {
+        Node node = new Node(data);
+        node.next = head;
+        head = node;
+        return head;
+    }
+
+
+    public Node reverseLinkList() {
+        if (head == null) {
+            return head;
+        }
+        Node reverseHead = null;
+        Node cur = head;
+        Node prev = null;
+        while (cur != null) {
+            Node next = cur.next;
+            if (next == null) {
+                reverseHead = cur;
+            }
+            cur.next = prev;
+            prev = cur;
+            cur = next;
+        }
+        return reverseHead;
+    }
+
+    /**
+     * 打印链表
+     */
+    public void printLinkList(Node head) {
+        Node cur = head;
+        while (cur != null) {
+            System.out.print(cur.data + " ");
+            cur = cur.next;
+        }
+    }
+
+    public Node getHead() {
+        return head;
+    }
+
+    public static class Node {
+        public int data;
+        public Node next;
+
+        public Node(int data) {
+            this.data = data;
+        }
+    }
+}
diff --git a/src/test/java/cn/byhieg/algorithmtutorialtest/SingleLinkListTest.java b/src/test/java/cn/byhieg/algorithmtutorialtest/SingleLinkListTest.java
@@ -0,0 +1,57 @@
+package cn.byhieg.algorithmtutorialtest;
+
+import cn.byhieg.algorithmtutorial.SingleLinkList;
+import junit.framework.TestCase;
+
+/**
+ * Created by byhieg on 17/5/2.
+ * Mail to byhieg@gmail.com
+ */
+public class SingleLinkListTest extends TestCase {
+
+
+    SingleLinkList linkList;
+
+    public void setUp() throws Exception {
+        super.setUp();
+        linkList = new SingleLinkList();
+    }
+
+    public void tearDown() throws Exception {
+//        linkList.printLinkList(linkList.head);
+//        System.out.println();
+    }
+
+
+    public void testInsertFromTail() throws Exception {
+//        linkList.insertFromTail(1);
+//        linkList.insertFromTail(2);
+//        linkList.insertFromTail(3);
+//        linkList.insertFromTail(4);
+//        linkList.insertFromTail(5);
+//        linkList.insertFromTail(6);
+//        System.out.println("尾插入");
+    }
+
+    public void testInsertFromHead() throws Exception {
+//        linkList.insertFromHead(1);
+//        linkList.insertFromHead(2);
+//        linkList.insertFromHead(3);
+//        linkList.insertFromHead(4);
+//        linkList.insertFromHead(5);
+//        linkList.insertFromHead(6);
+//        System.out.println("头插入");
+    }
+    public void testReverseLinkList() throws Exception {
+        linkList.insertFromHead(1);
+        linkList.insertFromHead(2);
+        linkList.insertFromHead(3);
+        linkList.insertFromHead(4);
+        linkList.insertFromHead(5);
+        linkList.insertFromHead(6);
+        linkList.printLinkList(linkList.reverseLinkList());
+    }
+    public void testGetHead() throws Exception {
+    }
+
+}
