Skip to content

Commit 7b55df1

Browse files
zztian1024zztian1024
committed
为链表篇 增加 Swift 实现
1 parent a16c030 commit 7b55df1

14 files changed

+499
-3
lines changed

‎animation-simulation/链表篇/234. 回文链表.md

Lines changed: 83 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -145,6 +145,35 @@ class Solution:
145145
return True
146146
```
147147

148+
Swift Code：
149+
150+
```swift
151+
class Solution {
152+
func isPalindrome(_ head: ListNode?) -> Bool {
153+
// 这里需要用动态数组，因为我们不知道链表的长度
154+
var arr:[Int?] = []
155+
var copynode = head
156+
// 将链表的值复制到数组中
157+
while copynode != nil {
158+
arr.append(copynode?.val)
159+
copynode = copynode?.next
160+
}
161+
// 双指针遍历数组
162+
var back = 0, pro = arr.count - 1
163+
while back < pro {
164+
// 判断两个指针的值是否相等
165+
if arr[pro] != arr[back] {
166+
return false
167+
}
168+
// 移动指针
169+
back += 1
170+
pro -= 1
171+
}
172+
return true
173+
}
174+
}
175+
```
176+
148177
这个方法可以直接通过，但是这个方法需要辅助数组，那我们还有其他更好的方法吗？
149178

150179
**双指针翻转链表法**
@@ -375,3 +404,57 @@ class Solution:
375404
return low
376405
```
377406

407+
Swift Code：
408+
409+
```swift
410+
class Solution {
411+
func isPalindrome(_ head: ListNode?) -> Bool {
412+
if head == nil || head?.next == nil {
413+
return true
414+
}
415+
//找到中间节点，也就是翻转的头节点,这个在昨天的题目中讲到
416+
//但是今天和昨天有一些不一样的地方就是，如果有两个中间节点返回第一个，昨天的题目是第二个
417+
var midnode = searchmidnode(head)
418+
//原地翻转链表，需要两个辅助指针。这个也是面试题目，大家可以做一下
419+
//这里我们用的是midnode.next需要注意，因为我们找到的是中点，但是我们翻转的是后半部分
420+
var backhalf = reverse(midnode?.next);
421+
//遍历两部分链表，判断值是否相等
422+
var p1 = head
423+
var p2 = backhalf
424+
while p2 != nil {
425+
if p1?.val != p2?.val {
426+
midnode?.next = reverse(backhalf)
427+
return false
428+
}
429+
p1 = p1?.next
430+
p2 = p2?.next
431+
}
432+
//还原链表并返回结果，这一步是需要注意的，我们不可以破坏初始结构，我们只是判断是否为回文，
433+
//当然如果没有这一步也是可以AC，但是面试的时候题目要求可能会有这一条。
434+
midnode?.next = reverse(backhalf)
435+
return true
436+
}
437+
//找到中点
438+
func searchmidnode(_ head: ListNode?) -> ListNode? {
439+
var fast = head, slow = head
440+
while fast?.next != nil && fast?.next?.next != nil {
441+
fast = fast?.next?.next
442+
slow = slow?.next
443+
}
444+
return slow
445+
}
446+
//翻转链表
447+
func reverse(_ slow: ListNode?) -> ListNode? {
448+
var slow = slow
449+
var low: ListNode?
450+
var temp: ListNode?
451+
while slow != nil {
452+
temp = slow?.next
453+
slow?.next = low
454+
low = slow
455+
slow = temp
456+
}
457+
return low
458+
}
459+
}
460+
```

‎animation-simulation/链表篇/leetcode141环形链表.md

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -108,3 +108,20 @@ class Solution:
108108
return False
109109
```
110110

111+
Swift Code：
112+
113+
```swift
114+
class Solution {
115+
func hasCycle(_ head: ListNode?) -> Bool {
116+
var fast = head, slow = head
117+
while fast != nil && fast?.next != nil {
118+
fast = fast?.next?.next
119+
slow = slow?.next
120+
if fast === slow {
121+
return true
122+
}
123+
}
124+
return false
125+
}
126+
}
127+
```

‎animation-simulation/链表篇/leetcode142环形链表2.md

Lines changed: 26 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -132,8 +132,6 @@ class Solution:
132132
return head
133133
```
134134

135-
136-
137135
### 快慢指针
138136

139137
这个方法是比较巧妙的方法，但是不容易想到，也不太容易理解，利用快慢指针判断是否有环很容易，但是判断环的入口就没有那么容易，之前说过快慢指针肯定会在环内相遇，见下图。
@@ -275,3 +273,29 @@ class Solution:
275273
return slow
276274
```
277275

276+
Swift Code：
277+
278+
```swift
279+
class Solution {
280+
func detectCycle(_ head: ListNode?) -> ListNode? {
281+
// 快慢指针
282+
var fast = head, slow = head
283+
while fast != nil && fast?.next != nil {
284+
fast = fast?.next?.next
285+
slow = slow?.next
286+
// 相遇
287+
if fast === slow {
288+
// 设置一个新的指针，从头节点出发，慢指针速度为1，所以可以使用慢指针从相遇点出发
289+
// 此处也可以不创新结点，直接将 fast = head
290+
var newNode = head
291+
while newNode !== slow {
292+
slow = slow?.next
293+
newNode = newNode?.next
294+
}
295+
return slow
296+
}
297+
}
298+
return nil
299+
}
300+
}
301+
```

‎animation-simulation/链表篇/leetcode147对链表进行插入排序.md

Lines changed: 37 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -225,5 +225,41 @@ class Solution:
225225
return dummyNode.next
226226
```
227227

228+
Swift Code：
228229

229-
230+
```swift
231+
class Solution {
232+
func insertionSortList(_ head: ListNode?) -> ListNode? {
233+
if head == nil && head?.next == nil {
234+
return head
235+
}
236+
//哑节点
237+
var dummyNode = ListNode(-1)
238+
dummyNode.next = head
239+
//pre负责指向新元素，last 负责指向新元素的前一元素
240+
//判断是否需要执行插入操作
241+
var pre = head?.next
242+
var last = head
243+
while pre != nil {
244+
//不需要插入到合适位置，则继续往下移动
245+
if last!.val <= pre!.val {
246+
pre = pre?.next
247+
last = last?.next
248+
continue
249+
}
250+
//开始出发，查找新元素的合适位置
251+
var temphead = dummyNode
252+
while temphead.next!.val <= pre!.val {
253+
temphead = temphead.next!
254+
}
255+
//此时我们已经找到了合适位置，我们需要进行插入，大家可以画一画
256+
last?.next = pre?.next
257+
pre?.next = temphead.next
258+
temphead.next = pre
259+
//继续往下移动
260+
pre = last?.next
261+
}
262+
return dummyNode.next
263+
}
264+
}
265+
```

‎animation-simulation/链表篇/leetcode206反转链表.md

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -138,6 +138,32 @@ class Solution:
138138
return low
139139
```
140140

141+
Swift Code:
142+
143+
```swift
144+
class Solution {
145+
func reverseList(_ head: ListNode?) -> ListNode? {
146+
// 边界条件
147+
if head == nil || head?.next == nil {
148+
return head
149+
}
150+
var pro = head
151+
var low: ListNode?
152+
while pro != nil {
153+
// 代表橙色指针
154+
var temp = pro
155+
// 移动绿色指针
156+
pro = pro?.next
157+
// 反转节点
158+
temp?.next = low
159+
// 移动黄色指针
160+
low = temp
161+
}
162+
return low
163+
}
164+
}
165+
```
166+
141167
上面的迭代写法是不是搞懂啦，现在还有一种递归写法，不是特别容易理解，刚开始刷题的同学，可以只看迭代解法。
142168

143169

@@ -227,6 +253,25 @@ class Solution:
227253
return pro
228254
```
229255

256+
Swift Code:
257+
258+
```swift
259+
class Solution {
260+
func reverseList(_ head: ListNode?) -> ListNode? {
261+
// 结束条件
262+
if head == nil || head?.next == nil {
263+
return head
264+
}
265+
var pro = reverseList(head?.next)
266+
// 将节点进行反转
267+
head?.next?.next = head
268+
// 防止循环
269+
head?.next = nil
270+
return pro
271+
}
272+
}
273+
```
274+
230275
<br/>
231276

232277
> 贡献者[@jaredliw](https://github.com/jaredliw)注：

‎animation-simulation/链表篇/leetcode328奇偶链表.md

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -128,3 +128,27 @@ class Solution:
128128
return head
129129
```
130130

131+
Swift Code：
132+
133+
```swift
134+
class Solution {
135+
func oddEvenList(_ head: ListNode?) -> ListNode? {
136+
if head == nil || head?.next == nil {
137+
return head
138+
}
139+
var odd = head
140+
var even = head?.next
141+
var evenHead = even
142+
while odd?.next != nil && even?.next != nil {
143+
//将偶数位合在一起，奇数位合在一起
144+
odd?.next = even?.next
145+
odd = odd?.next
146+
even?.next = odd?.next
147+
even = even?.next
148+
}
149+
//链接
150+
odd?.next = evenHead
151+
return head
152+
}
153+
}
154+
```

‎animation-simulation/链表篇/leetcode82删除排序链表中的重复元素II.md

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -165,3 +165,34 @@ class Solution:
165165
return dummy.next # 注意，这里传回的不是head，而是虚拟节点的下一个节点，head有可能已经换了
166166
```
167167

168+
Swift Code：
169+
170+
```swift
171+
class Solution {
172+
func deleteDuplicates(_ head: ListNode?) -> ListNode? {
173+
// 侦察兵指针
174+
var pre = head
175+
// 创建哑节点，接上head
176+
var dummy = ListNode(-1)
177+
dummy.next = head
178+
// 跟随的指针
179+
var low:ListNode? = dummy
180+
while pre != nil && pre?.next != nil {
181+
if pre?.val == pre?.next?.val {
182+
// 移动侦察兵指针直到找到与上一个不相同的元素
183+
while pre != nil && pre?.next != nil && pre?.val == pre?.next?.val {
184+
pre = pre?.next
185+
}
186+
// while循环后，pre停留在最后一个重复的节点上
187+
pre = pre?.next
188+
// 连上新节点
189+
low?.next = pre
190+
} else {
191+
pre = pre?.next
192+
low = low?.next
193+
}
194+
}
195+
return dummy.next // 注意，这里传回的不是head，而是虚拟节点的下一个节点，head有可能已经换了
196+
}
197+
}
198+
```

‎animation-simulation/链表篇/leetcode86分隔链表.md

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -157,3 +157,34 @@ class Solution:
157157
return headsmall.next
158158
```
159159

160+
Swift Code：
161+
162+
```swift
163+
class Solution {
164+
func partition(_ head: ListNode?, _ x: Int) -> ListNode? {
165+
var pro = head
166+
var big = ListNode(-1)
167+
var small = ListNode(-1)
168+
var headbig = big
169+
var headsmall = small
170+
//分
171+
while pro != nil {
172+
//大于时，放到 big 链表上
173+
if pro!.val >= x {
174+
big.next = pro
175+
big = big.next!
176+
//小于时，放到 small 链表上
177+
} else {
178+
small.next = pro
179+
small = small.next!
180+
}
181+
pro = pro?.next
182+
}
183+
//细节
184+
big.next = nil
185+
//合
186+
small.next = headbig.next
187+
return headsmall.next
188+
}
189+
}
190+
```

0 commit comments

Comments
 (0)