给出一个链表1->2->3->4->5和n=2,

通过移除倒数第二个节点,重新得到它的首节点,使链表输出成为1->2->3->5.

注:给出的n总是有效的
源代码

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
class ListNode:Equatable {
var node: Int
var nextNode: ListNode?
init(node: Int) {
self.node = node
}
public static func ==(lhs: ListNode, rhs: ListNode) -> Bool
{
return lhs.node == rhs.node && lhs.nextNode == rhs.nextNode
}
}
class Solution {
//输出链表
func showList(head: ListNode) {
var printStr: String = ""
var first = head.nextNode
while (first != nil) {
if first!.nextNode != nil {
printStr = printStr.appending("\(first!.node)->")
}else
{
printStr = printStr.appending("\(first!.node)")
}
first = first!.nextNode
}
let firstStr = String(head.node)
guard printStr != "" else {
print(firstStr)
return
}
printStr = firstStr.appending("->\(printStr)")
print(printStr)
}
func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
var h = head
var p1,p2,pre: ListNode?
if head == nil || n <= 0 {
return nil
}
p1 = head
p2 = head
var i = 0
//1.
while i < n-1 {
p1 = p1?.nextNode
if p1==nil {
return nil
}
i+=1
}
//2.
while p1?.nextNode != nil {
p1 = p1?.nextNode
//3.
pre = p2
p2 = p2?.nextNode
}
if p2 == head {
h = head?.nextNode
}else
{
//4.
pre?.nextNode = pre?.nextNode?.nextNode
}
// 5.
return h
}
}
  • 1.遍历n-1次,是为了获取到(2)中的p2位置.
  • 2.获取倒数n的节点
  • 3.此目的是为了要获取倒数节点的上一个节点,然后重新设置* (4)上一个节点的nextNode
  • 4.重新设置上一个节点的nextNode
  • 5.此步骤和以上步骤没有任何关系,只是重新返回头节点,保证输出是从head(头节点)开始