Leetcode 链表 算法练习

发表于 更新于 分类于 阅读次数：
本文字数： 4.4k 阅读时长 ≈ 7 分钟

Leetcode 链表 算法练习

算法与数据结构学习仓库地址：https://spiritling.coding.net/public/public/AaDS-docs-code/git/files
下面短网址失效的可以使用这个原始地址

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;
    }
}

手画图

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