Leetcode 链表 算法练习

Leetcode 链表 算法练习

237 删除链表中的节点

地址:https://leetcode-cn.com/problems/delete-node-in-a-linked-list/

代码:http://suo.im/6diowW

题目

请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。

解题思路

首先这个题目刚开始有点影响人的判断。

我以为函数中传入的是整个链表结构。(⊙﹏⊙)

然后就错了。。。

再次看题时,发现传入的是删除的节点,那么就简单了一部分

首先,要删除这个节点,常规来说就是通过改变上一节点的指向来删除节点。

但是很不幸的是,这个节点结构中是不存在 prev 指向,那么也就无法通过改变上一节点来删除。

既然这个节点存在,有值,有指向。

那么我们可不可以将这个节点的值改为下个节点的值,相应的这个节点的值就被删除了,其实是覆盖了。

改变了值,那么同样的需要改变 next 的指向,将其指向到下一个节点的下一个。

实际就是将下个节点复制到删除的节点这里,覆盖掉需要删除的节点。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
* }
*/
public class Solution {
public void DeleteNode(ListNode node) {
node.val=node.next.val;
node.next=node.next.next;
}
}

1290. 二进制链表转整数

地址:https://leetcode-cn.com/problems/convert-binary-number-in-a-linked-list-to-integer/

代码:http://suo.im/65MbOl

题目

给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。

请你返回该链表所表示数字的 十进制值 。

解题思路

第一版:

链表不是 1 就是 0,所以我想的是,直接将所有值拼接成字符串。

然后通过 c#自带的进制转换,将其二进制字符串转为十进制。

但是相应的,这个也有缺点,感觉没有对最前面为 0 的额外处理。

第二版:

利用进制转换算法,可以直接将二进制转为十进制,而不需要去调用其他方法。

并且直接使用传入进来的参数来进行赋值和操作。

代码

第一版:

时间复杂度分析:O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
* }
*/
public class Solution {
public int GetDecimalValue(ListNode head) {
// 追加判断,题目中是链表不为空,所以其实并不需要,但是为了养成好的代码习惯,还是加上了
if(head==null) return 0;
string str = "";
var current = head;
while (current != null)
{
str += current.val.ToString();
current = current.next;
}
return Convert.ToInt32(str,2);
}
}

第二版:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
* }
*/
public class Solution {
public int GetDecimalValue(ListNode head) {
int ans = 0;
while(head!=null){
ans = ans * 2 + head.val;
head = head.next;
}
return ans;
}
}

206. 反转链表

地址:https://leetcode-cn.com/problems/reverse-linked-list/

代码:http://suo.im/6e32hZ

题目

反转一个单链表

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

解题思路

第一版:首先反应想到的

时间复杂度:O(n^2)

看到题目第一时间想到的方式,首先将每个值拿出来,然后再将存放的数组反转下,在构建新的链表。

方式比较差劲,后续改进了下

第二版:递归方式

题目描述中,说可以使用迭代和递归方式进行。

创建个函数,处理每一个节点,将每个节点赋值新的节点,然后将传递进来的节点赋值到新的节点的 next 上,并且传递下个递归,层层下去

当按顺序传递进去的节点的 next 为 null 时,返回最后节点。

第三版:迭代方式

这个方式跑了两遍,第一遍 120 毫秒左右,第二遍跑了 104 毫秒 O(∩_∩)O 😄 。

迭代是一种不断用变量的旧值递推出新值的解决问题的方法。

所以在 while 循环链表时,将当前旧值赋值给新的节点,并且将新的节点 next 指向 prev

最后在反向赋值下,将临时的赋值给 prev

将 head 赋值为 head.next,继续循环,直到为 null

代码

第一版:首先想到的,比较差

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
public ListNode ReverseList(ListNode head)
{
// 普通方法
if (head==null || head.next ==null)
{
return head;
}
List<int> intList = new List<int>();
while (head != null)
{
intList.Add(head.val);
head = head.next;
}
intList.Reverse();
var newListNode = new ListNode(intList[0]);
for (int i = 1; i < intList.Count; i++)
{
var tempNode = new ListNode(intList[i])
{
next = null
};
var temp = newListNode;
while (temp.next != null)
{
temp = temp.next;
}
temp.next = tempNode;
}
return newListNode;
}

第二版:递归方式

1
2
3
4
5
6
7
8
9
10
11
12
public ListNode ReverseList2(ListNode head)
{
// 递归方式解决
return GetReverse(head, null);
ListNode GetReverse(ListNode current,ListNode res)
{
if (current == null) return res;
ListNode newNode = new ListNode(current.val);
newNode.next = res;
return GetReverse(current.next, newNode);
}
}

第三版:迭代方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public ListNode ReverseList3(ListNode head)
{
// 迭代方式解决
ListNode prev = null;
while (head != null)
{
// 将当前的赋值到temp
// 将temp引用改为prev
var temp = new ListNode(head.val)
{
next = prev
};
// 再将temp赋值到prev,覆盖掉
prev = temp;
head = head.next;
}
return prev;
}

O(∩_∩)O 😄 这个方式跑了两遍,第一遍 120 毫秒左右,第二遍跑了 104 毫秒。

876. 链表的中间结点

地址:https://leetcode-cn.com/problems/middle-of-the-linked-list/

代码:http://suo.im/65XknP

解题思路

找出中间值,一旦涉及到中间的处理,在链表中都可以使用快慢指针的方式

快指针每次两步

慢指针每次一步

当快指针为 null 或者它的下一个是 null

则证明到了末尾,然后同时返回慢指针的值(这个题好处就是如果是两个中间返回后一个),就是剩余的后半部分

具体末尾图看图

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode MiddleNode(ListNode head) {
if(head.next == null) return head;
// 一次前进两格
ListNode quick = head;
while (quick != null && quick.next != null)
{
quick = quick.next.next;
head = head.next;
}
return head;
}
}

手画图

-------文章到此结束  感谢您的阅读-------