上海网站设计 企业短视频seo排名加盟
今日任务
- 链表理论基础
- 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;}
}