【两个月算法速成】day03-链表-Toy模板网

这篇具有很好参考价值的文章主要介绍了【两个月算法速成】day03-链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

203. 移除链表元素

题目链接

思路

代码

206. 反转链表

题目链接

思路

代码

总结

203. 移除链表元素

题目链接

力扣

思路

如下图所示就是移除链表的过程

【两个月算法速成】day03-链表

但是值得注意的是，移除头节点和其他位置的节点是不一样的，以为头结点前面没有节点。

所以如何移除头结点，可以设置一个虚拟节点指向头结点，这样链表的所有节点的删除都可以一样删除了

如何设置头结点：

【两个月算法速成】day03-链表

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode node = new ListNode(-1,head);
        ListNode pre = node;
        ListNode cur = head;
        while (cur != null){
            if (cur.val == val){
                pre.next = cur.next;
            }else{
                pre = cur;
            }
            cur = cur.next;
        }
       return node.next;
    }
}

文章来源地址https://www.toymoban.com/news/detail-424437.html

206. 反转链表

题目链接

力扣

思路

首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。

然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。

为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。

接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。

最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。此时我们return pre指针就可以了，pre指针就指向了新的头结点。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode temp = null;
        ListNode cur = head;
        ListNode node = null;
        while (cur != null){
            temp = cur.next;
            cur.next = node;
            node=cur;
            cur = temp;
        }
        return node;
    }
}