0%

leetcodeDay8

今日leetcode两题分别是删除链表的倒数第N个节点和反转链表,系简单难度的链表算法题

删除链表的倒数第N个节点

给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。

示例:

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

当删除了倒数第二个节点后,链表变为 1->2->3->5.

说明:

给定的 n 保证是有效的。

进阶:

你能尝试使用一趟扫描实现吗?

解答

该题最简单的想法就是先遍历一次,求出链表的长度,用长度减去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
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeNthFromEnd(head *ListNode, n int) *ListNode {
node := head
lLen := listLen(node)

//when node to be delete is the head, return the head's next
if lLen == n {
return head.Next
}
for i := 0; i < lLen-n-1; i++ {
node = node.Next
}
node.Next = node.Next.Next
return head
}

//calculate length of the list
func listLen(head *ListNode) (res int) {
node := head
for node != nil {
res++
node = node.Next
}
return
}

一次扫描实现…我能想到的办法是设置两个节点,它们之间距离为n.在第一次遍历的时候同时移动它们,当一个节点到达链表尾部时,另一个节点则是要删除的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func removeNthFromEnd(head *ListNode, n int) *ListNode {
node := head
//the node to be delete
toDelNode := head
//make the distance between 2 nodes be n
for i := 0; i < n-1; i++ {
node = node.Next
}
//return head's next when node to be delete is the head
if node.Next == nil {
return head.Next
}
//move node and toDelNode at the same time until node becomes end of the list
for node.Next.Next != nil {
node = node.Next
toDelNode = toDelNode.Next
}
//delete the node
toDelNode.Next = toDelNode.Next.Next
return head
}

总感觉删除节点的方式怪怪的,因为在链表中如果想要删除一个节点,则需要控制该节点的前一个节点

之前看课本上创建一个链表时,头结点是一个空节点,它的Next字段指向真正的带有信息的节点.这样的话,不会出现找到一个节点,如果想要删除它还得需要找到它的前一个节点的情况.或者我以后可以试一试

反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?

解答

看起来容易,实际上感觉好难啊…而且我只会使用迭代的方法-.-

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func reverseList(head *ListNode) *ListNode {
if head == nil {
return nil
}
resHead := head
head = head.Next
resHead.Next = nil

for head != nil {
node := head.Next
head.Next = resHead
resHead = head
head = node
}
return resHead
}