Day03

今日任务

• 链表理论基础
• 203.移除链表元素
• 707.设计链表
• 206.反转链表

---

链表理论基础

1）单链表

单链表中的指针域只能指向节点的下一个节点

2）双链表

双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点

双链表 既可以向前查询也可以向后查询

3）循环链表

链表首尾相连

---

链表的存储方式

链表在内存中可不是连续分布，是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理

---

链表操作

1）删除节点

2）添加节点?

---

?203?移除链表元素

题目链接：https://leetcode.cn/problems/remove-linked-list-elements/description/

移除元素简单，注意就是需要增加一个节点作为头节点，以免因为第一个元素被移除后，丢失了链表；然后遍历链表进行删除操作

/**
 * 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) {
        if(head == null) {
            return head;
        }
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode tmp = dummyHead;
        while(tmp.next != null) {
            if(tmp.next.val == val) {
                tmp.next = tmp.next.next;
            }else {
                tmp = tmp.next;
            }
        }
        return dummyHead.next;
    }
}

---

707 设计链表

题目链接：https://leetcode.cn/problems/design-linked-list/

实现链表的基本操作，直接在力扣完成，过程略；

---

206 反转链表

题目链接：https://leetcode.cn/problems/reverse-linked-list/description/

这个是单链表的反转

思路：增加一个第一个元素 null?

• 遍历元素，先需要暂存当前元素其后继节点
• 然后使当前元素之前其前面的元素
• 再保存当前元素节点
• 访问下一个元素

/**
 * 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 cur = head, pre = null;;
        while(cur != null) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}