Skip to content

Commit da550ba

Browse files
yanglbmeyanglbme
committed
feat: add python and java solutions to leetcode problem: No.0148
1 parent a35b68a commit da550ba

File tree

10 files changed

+285
-38
lines changed

10 files changed

+285
-38
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -60,6 +60,7 @@
6060
1. [链表中倒数第 k 个节点](/lcci/02.02.Kth%20Node%20From%20End%20of%20List/README.md)
6161
1. [合并两个有序链表](/solution/0000-0099/0021.Merge%20Two%20Sorted%20Lists/README.md)
6262
1. [合并 K 个排序链表](/solution/0000-0099/0023.Merge%20k%20Sorted%20Lists/README.md)
63+
1. [排序链表](/solution/0100-0199/0148.Sort%20List/README.md)
6364
1. [反转链表](/solution/0200-0299/0206.Reverse%20Linked%20List/README.md)
6465
1. [回文链表](/solution/0200-0299/0234.Palindrome%20Linked%20List/README.md)
6566
1. [环形链表](/solution/0100-0199/0141.Linked%20List%20Cycle/README.md)

‎README_EN.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -58,6 +58,7 @@ Complete solutions to [LeetCode](https://leetcode-cn.com/problemset/all/), [LCOF
5858
1. [Kth Node From End of List](/lcci/02.02.Kth%20Node%20From%20End%20of%20List/README_EN.md)
5959
1. [Merge Two Sorted Lists](/solution/0000-0099/0021.Merge%20Two%20Sorted%20Lists/README_EN.md)
6060
1. [Merge k Sorted Lists](/solution/0000-0099/0023.Merge%20k%20Sorted%20Lists/README_EN.md)
61+
1. [Sort List](/solution/0100-0199/0148.Sort%20List/README_EN.md)
6162
1. [Reverse Linked List](/solution/0200-0299/0206.Reverse%20Linked%20List/README_EN.md)
6263
1. [Palindrome Linked List](/solution/0200-0299/0234.Palindrome%20Linked%20List/README_EN.md)
6364
1. [Linked List Cycle](/solution/0100-0199/0141.Linked%20List%20Cycle/README_EN.md)

‎solution/0000-0099/0024.Swap Nodes in Pairs/README.md

Lines changed: 24 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -27,6 +27,15 @@
2727
<!-- 这里可写当前语言的特殊实现逻辑 -->
2828

2929
```python
30+
# Definition for singly-linked list.
31+
# class ListNode:
32+
# def __init__(self, val=0, next=None):
33+
# self.val = val
34+
# self.next = next
35+
class Solution:
36+
def swapPairs(self, head: ListNode) -> ListNode:
37+
if head is None or head.next is None:
38+
return head
3039

3140
```
3241

@@ -35,7 +44,21 @@
3544
<!-- 这里可写当前语言的特殊实现逻辑 -->
3645

3746
```java
38-
47+
/**
48+
* Definition for singly-linked list.
49+
* public class ListNode {
50+
* int val;
51+
* ListNode next;
52+
* ListNode() {}
53+
* ListNode(int val) { this.val = val; }
54+
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
55+
* }
56+
*/
57+
class Solution {
58+
public ListNode swapPairs(ListNode head) {
59+
60+
}
61+
}
3962
```
4063

4164
### **...**

‎solution/0000-0099/0024.Swap Nodes in Pairs/README_EN.md

Lines changed: 22 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -25,13 +25,33 @@ Given <code>1-&gt;2-&gt;3-&gt;4</code>, you should return the list as <code>2-&g
2525
### **Python3**
2626

2727
```python
28-
28+
# Definition for singly-linked list.
29+
# class ListNode:
30+
# def __init__(self, val=0, next=None):
31+
# self.val = val
32+
# self.next = next
33+
class Solution:
34+
def swapPairs(self, head: ListNode) -> ListNode:
2935
```
3036

3137
### **Java**
3238

3339
```java
34-
40+
/**
41+
* Definition for singly-linked list.
42+
* public class ListNode {
43+
* int val;
44+
* ListNode next;
45+
* ListNode() {}
46+
* ListNode(int val) { this.val = val; }
47+
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
48+
* }
49+
*/
50+
class Solution {
51+
public ListNode swapPairs(ListNode head) {
52+
53+
}
54+
}
3555
```
3656

3757
### **...**

‎solution/0100-0199/0148.Sort List/README.md

Lines changed: 69 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -22,22 +22,89 @@
2222

2323
<!-- 这里可写通用的实现逻辑 -->
2424

25+
先用快慢指针找到链表中点，然后分成左右两个链表，递归排序左右链表。最后合并两个排序的链表即可。
26+
2527
<!-- tabs:start -->
2628

2729
### **Python3**
2830

2931
<!-- 这里可写当前语言的特殊实现逻辑 -->
3032

3133
```python
32-
34+
# Definition for singly-linked list.
35+
# class ListNode:
36+
# def __init__(self, val=0, next=None):
37+
# self.val = val
38+
# self.next = next
39+
class Solution:
40+
def sortList(self, head: ListNode) -> ListNode:
41+
if head is None or head.next is None:
42+
return head
43+
slow, fast = head, head.next
44+
while fast and fast.next:
45+
slow, fast = slow.next, fast.next.next
46+
t = slow.next
47+
slow.next = None
48+
l1, l2 = self.sortList(head), self.sortList(t)
49+
dummy = ListNode()
50+
cur = dummy
51+
while l1 and l2:
52+
if l1.val <= l2.val:
53+
cur.next = l1
54+
l1 = l1.next
55+
else:
56+
cur.next = l2
57+
l2 = l2.next
58+
cur = cur.next
59+
cur.next = l1 or l2
60+
return dummy.next
3361
```
3462

3563
### **Java**
3664

3765
<!-- 这里可写当前语言的特殊实现逻辑 -->
3866

3967
```java
40-
68+
/**
69+
* Definition for singly-linked list.
70+
* public class ListNode {
71+
* int val;
72+
* ListNode next;
73+
* ListNode() {}
74+
* ListNode(int val) { this.val = val; }
75+
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
76+
* }
77+
*/
78+
class Solution {
79+
public ListNode sortList(ListNode head) {
80+
if (head == null || head.next == null) {
81+
return head;
82+
}
83+
ListNode slow = head, fast = head.next;
84+
while (fast != null && fast.next != null) {
85+
slow = slow.next;
86+
fast = fast.next.next;
87+
}
88+
ListNode t = slow.next;
89+
slow.next = null;
90+
ListNode l1 = sortList(head);
91+
ListNode l2 = sortList(t);
92+
ListNode dummy = new ListNode(0);
93+
ListNode cur = dummy;
94+
while (l1 != null && l2 != null) {
95+
if (l1.val <= l2.val) {
96+
cur.next = l1;
97+
l1 = l1.next;
98+
} else {
99+
cur.next = l2;
100+
l2 = l2.next;
101+
}
102+
cur = cur.next;
103+
}
104+
cur.next = l1 == null ? l2 : l1;
105+
return dummy.next;
106+
}
107+
}
41108
```
42109

43110
### **...**

‎solution/0100-0199/0148.Sort List/README_EN.md

Lines changed: 67 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -31,13 +31,78 @@
3131
### **Python3**
3232

3333
```python
34-
34+
# Definition for singly-linked list.
35+
# class ListNode:
36+
# def __init__(self, val=0, next=None):
37+
# self.val = val
38+
# self.next = next
39+
class Solution:
40+
def sortList(self, head: ListNode) -> ListNode:
41+
if head is None or head.next is None:
42+
return head
43+
slow, fast = head, head.next
44+
while fast and fast.next:
45+
slow, fast = slow.next, fast.next.next
46+
t = slow.next
47+
slow.next = None
48+
l1, l2 = self.sortList(head), self.sortList(t)
49+
dummy = ListNode()
50+
cur = dummy
51+
while l1 and l2:
52+
if l1.val <= l2.val:
53+
cur.next = l1
54+
l1 = l1.next
55+
else:
56+
cur.next = l2
57+
l2 = l2.next
58+
cur = cur.next
59+
cur.next = l1 or l2
60+
return dummy.next
3561
```
3662

3763
### **Java**
3864

3965
```java
40-
66+
/**
67+
* Definition for singly-linked list.
68+
* public class ListNode {
69+
* int val;
70+
* ListNode next;
71+
* ListNode() {}
72+
* ListNode(int val) { this.val = val; }
73+
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
74+
* }
75+
*/
76+
class Solution {
77+
public ListNode sortList(ListNode head) {
78+
if (head == null || head.next == null) {
79+
return head;
80+
}
81+
ListNode slow = head, fast = head.next;
82+
while (fast != null && fast.next != null) {
83+
slow = slow.next;
84+
fast = fast.next.next;
85+
}
86+
ListNode t = slow.next;
87+
slow.next = null;
88+
ListNode l1 = sortList(head);
89+
ListNode l2 = sortList(t);
90+
ListNode dummy = new ListNode(0);
91+
ListNode cur = dummy;
92+
while (l1 != null && l2 != null) {
93+
if (l1.val <= l2.val) {
94+
cur.next = l1;
95+
l1 = l1.next;
96+
} else {
97+
cur.next = l2;
98+
l2 = l2.next;
99+
}
100+
cur = cur.next;
101+
}
102+
cur.next = l1 == null ? l2 : l1;
103+
return dummy.next;
104+
}
105+
}
41106
```
42107

43108
### **...**

‎solution/0100-0199/0148.Sort List/Solution.java

Lines changed: 30 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -1,34 +1,40 @@
1+
/**
2+
* Definition for singly-linked list.
3+
* public class ListNode {
4+
* int val;
5+
* ListNode next;
6+
* ListNode() {}
7+
* ListNode(int val) { this.val = val; }
8+
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9+
* }
10+
*/
111
class Solution {
212
public ListNode sortList(ListNode head) {
3-
if(head == null || head.next == null) return head;
4-
int len = 0;
5-
ListNode cur = head;
6-
while(cur != null){
7-
len++;
8-
cur = cur.next;
13+
if (head == null || head.next == null) {
14+
return head;
15+
}
16+
ListNode slow = head, fast = head.next;
17+
while (fast != null && fast.next != null) {
18+
slow = slow.next;
19+
fast = fast.next.next;
920
}
10-
ListNode left = head,right = head;
11-
for(int i = 0; i < len/2 - 1; i++) right = right.next;
12-
ListNode leftTail = right;
13-
right = right.next;
14-
leftTail.next = null;
15-
left = sortList(left);
16-
right = sortList(right);
21+
ListNode t = slow.next;
22+
slow.next = null;
23+
ListNode l1 = sortList(head);
24+
ListNode l2 = sortList(t);
1725
ListNode dummy = new ListNode(0);
18-
cur = dummy;
19-
while(left != null && right != null){
20-
if(left.val < right.val){
21-
cur.next = left;
22-
left = left.next;
23-
}else{
24-
cur.next = right;
25-
right = right.next;
26+
ListNode cur = dummy;
27+
while (l1 != null && l2 != null) {
28+
if (l1.val <= l2.val) {
29+
cur.next = l1;
30+
l1 = l1.next;
31+
} else {
32+
cur.next = l2;
33+
l2 = l2.next;
2634
}
2735
cur = cur.next;
2836
}
29-
if(left != null) cur.next = left;
30-
else if(right != null) cur.next = right;
31-
else cur.next = null;
37+
cur.next = l1 == null ? l2 : l1;
3238
return dummy.next;
3339
}
3440
}

‎solution/0100-0199/0148.Sort List/Solution.py

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
# Definition for singly-linked list.
2+
# class ListNode:
3+
# def __init__(self, val=0, next=None):
4+
# self.val = val
5+
# self.next = next
6+
class Solution:
7+
def sortList(self, head: ListNode) -> ListNode:
8+
if head is None or head.next is None:
9+
return head
10+
slow, fast = head, head.next
11+
while fast and fast.next:
12+
slow, fast = slow.next, fast.next.next
13+
t = slow.next
14+
slow.next = None
15+
l1, l2 = self.sortList(head), self.sortList(t)
16+
dummy = ListNode()
17+
cur = dummy
18+
while l1 and l2:
19+
if l1.val <= l2.val:
20+
cur.next = l1
21+
l1 = l1.next
22+
else:
23+
cur.next = l2
24+
l2 = l2.next
25+
cur = cur.next
26+
cur.next = l1 or l2
27+
return dummy.next

‎solution/0300-0399/0328.Odd Even Linked List/README.md

Lines changed: 22 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -38,15 +38,35 @@
3838
<!-- 这里可写当前语言的特殊实现逻辑 -->
3939

4040
```python
41-
41+
# Definition for singly-linked list.
42+
# class ListNode:
43+
# def __init__(self, val=0, next=None):
44+
# self.val = val
45+
# self.next = next
46+
class Solution:
47+
def oddEvenList(self, head: ListNode) -> ListNode:
4248
```
4349

4450
### **Java**
4551

4652
<!-- 这里可写当前语言的特殊实现逻辑 -->
4753

4854
```java
49-
55+
/**
56+
* Definition for singly-linked list.
57+
* public class ListNode {
58+
* int val;
59+
* ListNode next;
60+
* ListNode() {}
61+
* ListNode(int val) { this.val = val; }
62+
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
63+
* }
64+
*/
65+
class Solution {
66+
public ListNode oddEvenList(ListNode head) {
67+
68+
}
69+
}
5070
```
5171

5272
### **...**

0 commit comments

Comments
 (0)