Skip to content

Commit c9f6cea

Browse files
coderacademyonlinecoderacademyonline
committed
leetcode题
1 parent 18359a7 commit c9f6cea

File tree

4 files changed

+287
-0
lines changed

4 files changed

+287
-0
lines changed

‎java-leetcode/src/leetcode/link/LeetCode141.java

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package leetcode.link;
2+
3+
/**
4+
* <p>
5+
* 给定一个链表，判断链表中是否有环。
6+
7+
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
8+
输入：head = [1,2], pos = 0
9+
输出：true
10+
解释：链表中有一个环，其尾部连接到第一个节点。
11+
* </p>
12+
*
13+
* @author jwzhao
14+
* @version 1.0
15+
* @date 2019/3/25 18:37
16+
*/
17+
public class LeetCode141 {
18+
19+
public boolean hasCycle(ListNode head) {
20+
if (head == null){
21+
return false;
22+
}
23+
ListNode slow = head;
24+
ListNode fast = head;
25+
while (slow !=null && fast != null && fast.next != null){
26+
slow = slow.next;
27+
fast = fast.next.next;
28+
if (slow!=null && fast!=null && slow == fast){
29+
return true;
30+
}
31+
}
32+
33+
return false;
34+
}
35+
}

‎java-leetcode/src/leetcode/link/LeetCode160.java

Lines changed: 107 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,107 @@
1+
package leetcode.link;
2+
3+
import java.util.LinkedHashMap;
4+
import java.util.Map;
5+
6+
/**
7+
* <p>
8+
* 编写一个程序，找到两个单链表相交的起始节点。
9+
* </p>
10+
*
11+
* @author jwzhao
12+
* @version 1.0
13+
* @date 2019/3/26 09:51
14+
*/
15+
public class LeetCode160 {
16+
17+
/**
18+
* 思路：将环首尾相连，如果是相交，则他是一个环形链表，则找到环形链表的入口即可
19+
* @param headA
20+
* @param headB
21+
* @return
22+
*/
23+
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
24+
if (headA == null || headB == null){
25+
return null;
26+
}
27+
ListNode nodeA = headA;
28+
while (nodeA.next != null){
29+
nodeA=nodeA.next;
30+
}
31+
nodeA.next = headB;
32+
// 接下来要找出环形的入口
33+
ListNode fast = headA;
34+
ListNode slow = headA;
35+
while (slow != null && fast!=null && fast.next != null){
36+
slow = slow.next;
37+
fast = fast.next.next;
38+
if (slow == fast){
39+
if (slow == null){
40+
nodeA.next = null;
41+
return null;
42+
}
43+
// 此时说明现在首尾相连后是一个环形链表，也可以判断出来是一个相交链表
44+
ListNode meetNode = slow;
45+
ListNode node = headA;
46+
while (meetNode != node){
47+
meetNode = meetNode.next;
48+
node = node.next;
49+
}
50+
nodeA.next = null;
51+
return meetNode;
52+
}
53+
}
54+
nodeA.next = null;
55+
return null;
56+
}
57+
58+
/**
59+
* 思路：去掉两个链表的长度差值之后，循环两个指针，直到相等
60+
* @param headA
61+
* @param headB
62+
* @return
63+
*/
64+
public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
65+
if (headA == null || headB == null){
66+
return null;
67+
}
68+
int lengthA = 0;
69+
ListNode nodeA = headA;
70+
while (nodeA!=null){
71+
nodeA = nodeA.next;
72+
lengthA++;
73+
}
74+
75+
int lengthB = 0;
76+
ListNode nodeB = headB;
77+
while (nodeB != null){
78+
nodeB = nodeB.next;
79+
lengthB++;
80+
}
81+
// 去掉链表的差长度，找到相同的起点
82+
ListNode pA = headA;
83+
ListNode pB = headB;
84+
if (lengthA>lengthB){
85+
int length = lengthA-lengthB;
86+
while (length >0){
87+
pA = pA.next;
88+
length--;
89+
}
90+
}else {
91+
int length = lengthB-lengthA;
92+
while (length>0){
93+
pB = pB.next;
94+
length--;
95+
}
96+
}
97+
while (pA!=null && pB!=null){
98+
if (pA == pB){
99+
return pA;
100+
}
101+
pA = pA.next;
102+
pB = pB.next;
103+
}
104+
105+
return null;
106+
}
107+
}

‎java-leetcode/src/leetcode/link/LeetCode203.java

Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,82 @@
1+
package leetcode.link;
2+
3+
/**
4+
* <p>
5+
* 删除链表中等于给定值 val 的所有节点。
6+
示例:
7+
输入: 1->2->6->3->4->5->6, val = 6
8+
输出: 1->2->3->4->5
9+
* </p>
10+
*
11+
* @author jwzhao
12+
* @version 1.0
13+
* @date 2019/3/26 18:16
14+
*/
15+
public class LeetCode203 {
16+
17+
public static void main(String[] args) {
18+
int[] datas = {1,2,2,1};
19+
ListNode listNode = null;
20+
for(int data:datas){
21+
ListNode thisNode = new ListNode(data);
22+
if (listNode == null){
23+
listNode = thisNode;
24+
}else {
25+
ListNode tempNode = listNode;
26+
while (tempNode.next != null){
27+
tempNode = tempNode.next;
28+
}
29+
tempNode.next = thisNode;
30+
}
31+
}
32+
LeetCode203 leetCode203 = new LeetCode203();
33+
leetCode203.display(leetCode203.removeElements(listNode,2));
34+
}
35+
36+
public ListNode removeElements(ListNode head, int val) {
37+
if (head == null){
38+
return null;
39+
}
40+
41+
ListNode currNode = head;
42+
ListNode preNode = head;
43+
while (currNode != null){
44+
if (currNode.val == val){
45+
if (currNode == head){
46+
// 删除头结点
47+
head = head.next;
48+
}else {
49+
preNode.next = currNode.next;
50+
currNode = head;
51+
continue;
52+
}
53+
}
54+
preNode = currNode;
55+
currNode = currNode.next;
56+
}
57+
58+
return head;
59+
}
60+
61+
62+
public ListNode removeElements1(ListNode head, int val) {
63+
ListNode header = new ListNode(-1);
64+
header.next = head;
65+
ListNode cur = header;
66+
while(cur.next != null){
67+
if(cur.next.val == val ){
68+
cur.next = cur.next.next;
69+
}else{
70+
cur = cur.next;
71+
}
72+
}
73+
return header.next;
74+
}
75+
76+
public void display(ListNode listNode){
77+
while (listNode != null){
78+
System.err.print(listNode.val+",");
79+
listNode = listNode.next;
80+
}
81+
}
82+
}

‎java-leetcode/src/leetcode/link/LeetCode83.java

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
package leetcode.link;
2+
3+
/**
4+
* <p>
5+
* 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
6+
* 例：
7+
* 输入: 1->1->1->2->3->3->3->3
8+
输出: 1->2->3
9+
* </p>
10+
*
11+
* @author jwzhao
12+
* @version 1.0
13+
* @date 2019/3/25 16:46
14+
*/
15+
public class LeetCode83 {
16+
17+
public static void main(String[] args) {
18+
int[] datas = {1,1,1,2,3,3};
19+
ListNode listNode = null;
20+
for(int data:datas){
21+
ListNode thisNode = new ListNode(data);
22+
if (listNode == null){
23+
listNode = thisNode;
24+
}else {
25+
ListNode tempNode = listNode;
26+
while (tempNode.next != null){
27+
tempNode = tempNode.next;
28+
}
29+
tempNode.next = thisNode;
30+
}
31+
}
32+
LeetCode83 leetCode83 = new LeetCode83();
33+
leetCode83.display(leetCode83.deleteDuplicates(listNode));
34+
}
35+
36+
public ListNode deleteDuplicates(ListNode head) {
37+
if (head == null){
38+
return null;
39+
}
40+
41+
ListNode p1 = head;
42+
ListNode p2 = head.next;
43+
while (p1!=null && p1.next != null && p2 != null){
44+
if (p1.val == p2.val){
45+
// 删除p2
46+
p1.next = p1.next.next;
47+
}else{
48+
p1 = p1.next;
49+
}
50+
p2 = p2.next;
51+
52+
}
53+
54+
return head;
55+
}
56+
57+
public void display(ListNode listNode){
58+
while (listNode != null){
59+
System.err.print(listNode.val+",");
60+
listNode = listNode.next;
61+
}
62+
}
63+
}

0 commit comments

Comments
 (0)