Skip to content

Commit 8632db2

Browse files
byhiegbyhieg
committed
添加单链表的相关算法
1 parent 02de769 commit 8632db2

3 files changed

Lines changed: 174 additions & 0 deletions

File tree

‎src/main/java/cn/byhieg/algorithmtutorial/BinaryTree.java‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -242,6 +242,32 @@ public static void mirror(Node root) {
242242
}
243243
}
244244

245+
/**
246+
* 得到两个节点的最近公共祖先节点。
247+
* 递归左右子树，如果返回的值都不为空，则表示在左右子树各找到一个target，因为最近的祖先就是cur
248+
* 如果有一个为空，则就不为空就是最近公共祖先。
249+
* @param root
250+
* @param target1
251+
* @param target2
252+
* @return
253+
*/
254+
public static Node findLCA(Node root, Node target1, Node target2) {
255+
if (root == null)
256+
return null;
257+
258+
if (root == target1 || root == target2) {
259+
return root;
260+
}
261+
Node left = findLCA(root.left, target1, target2);
262+
Node right = findLCA(root.right, target1, target2);
263+
if (left != null && right != null) {
264+
return root;
265+
}
266+
return left != null ? left:right;
267+
}
268+
269+
270+
245271
public static class Node {
246272
public int data;
247273
public Node left;
@@ -254,4 +280,6 @@ public Node(int data) {
254280
right = null;
255281
}
256282
}
283+
284+
257285
}

‎src/main/java/cn/byhieg/algorithmtutorial/SingleLinkList.java‎

Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
package cn.byhieg.algorithmtutorial;
2+
3+
/**
4+
* Created by byhieg on 17/5/2.
5+
* Mail to byhieg@gmail.com
6+
*/
7+
public class SingleLinkList {
8+
9+
10+
public Node head;
11+
12+
/**
13+
* 在当前链表尾部插入一个节点
14+
*
15+
* @param data
16+
* @return
17+
*/
18+
public Node insertFromTail(int data) {
19+
Node cur = getHead();
20+
Node node = new Node(data);
21+
if (cur == null) {
22+
head = node;
23+
return head;
24+
} else {
25+
while (cur.next != null) {
26+
cur = cur.next;
27+
}
28+
cur.next = node;
29+
}
30+
return cur;
31+
}
32+
33+
/**
34+
* 在当前链表头部插入一个节点
35+
*
36+
* @param data
37+
* @return
38+
*/
39+
public Node insertFromHead(int data) {
40+
Node node = new Node(data);
41+
node.next = head;
42+
head = node;
43+
return head;
44+
}
45+
46+
47+
public Node reverseLinkList() {
48+
if (head == null) {
49+
return head;
50+
}
51+
Node reverseHead = null;
52+
Node cur = head;
53+
Node prev = null;
54+
while (cur != null) {
55+
Node next = cur.next;
56+
if (next == null) {
57+
reverseHead = cur;
58+
}
59+
cur.next = prev;
60+
prev = cur;
61+
cur = next;
62+
}
63+
return reverseHead;
64+
}
65+
66+
/**
67+
* 打印链表
68+
*/
69+
public void printLinkList(Node head) {
70+
Node cur = head;
71+
while (cur != null) {
72+
System.out.print(cur.data + " ");
73+
cur = cur.next;
74+
}
75+
}
76+
77+
public Node getHead() {
78+
return head;
79+
}
80+
81+
public static class Node {
82+
public int data;
83+
public Node next;
84+
85+
public Node(int data) {
86+
this.data = data;
87+
}
88+
}
89+
}

‎src/test/java/cn/byhieg/algorithmtutorialtest/SingleLinkListTest.java‎

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
package cn.byhieg.algorithmtutorialtest;
2+
3+
import cn.byhieg.algorithmtutorial.SingleLinkList;
4+
import junit.framework.TestCase;
5+
6+
/**
7+
* Created by byhieg on 17/5/2.
8+
* Mail to byhieg@gmail.com
9+
*/
10+
public class SingleLinkListTest extends TestCase {
11+
12+
13+
SingleLinkList linkList;
14+
15+
public void setUp() throws Exception {
16+
super.setUp();
17+
linkList = new SingleLinkList();
18+
}
19+
20+
public void tearDown() throws Exception {
21+
// linkList.printLinkList(linkList.head);
22+
// System.out.println();
23+
}
24+
25+
26+
public void testInsertFromTail() throws Exception {
27+
// linkList.insertFromTail(1);
28+
// linkList.insertFromTail(2);
29+
// linkList.insertFromTail(3);
30+
// linkList.insertFromTail(4);
31+
// linkList.insertFromTail(5);
32+
// linkList.insertFromTail(6);
33+
// System.out.println("尾插入");
34+
}
35+
36+
public void testInsertFromHead() throws Exception {
37+
// linkList.insertFromHead(1);
38+
// linkList.insertFromHead(2);
39+
// linkList.insertFromHead(3);
40+
// linkList.insertFromHead(4);
41+
// linkList.insertFromHead(5);
42+
// linkList.insertFromHead(6);
43+
// System.out.println("头插入");
44+
}
45+
public void testReverseLinkList() throws Exception {
46+
linkList.insertFromHead(1);
47+
linkList.insertFromHead(2);
48+
linkList.insertFromHead(3);
49+
linkList.insertFromHead(4);
50+
linkList.insertFromHead(5);
51+
linkList.insertFromHead(6);
52+
linkList.printLinkList(linkList.reverseLinkList());
53+
}
54+
public void testGetHead() throws Exception {
55+
}
56+
57+
}

0 commit comments

Comments
 (0)