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
}
0%