LeetCode 203.移除链表元素
题目描述
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
题目链接
https://leetcode.cn/problems/remove-linked-list-elements/description/
解题思路
创建两个节点 prev和 cur，一个记录待删除元素的前一个节点，一个用来搜索节点。
删除时只需 prev的 next指向满足条件的 cur即可
// 耗时: 10m56s
class Solution {
public ListNode removeElements(ListNode head, int val) {
while (head != null && head.val == val) {
head = head.next;
}
if (head == null) {
return head;
}
ListNode node = head.next, cur = head;
while (node != null) {
while (node != null && node.val == val) {
node = node.next;
}
cur.next = node;
cur = cur.next;
if (node != null){
node = node.next;
}
}
return head;
}
}
LeetCode 707.设计链表
题目描述
你可以选择使用单链表或者双链表，设计并实现自己的链表。
单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。
如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
实现 MyLinkedList 类：
MyLinkedList()初始化MyLinkedList对象。int get(int index)获取链表中下标为index的节点的值。如果下标无效，则返回-1。void addAtHead(int val)将一个值为val的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。void addAtTail(int val)将一个值为val的节点追加到链表中作为链表的最后一个元素。void addAtIndex(int index, int val)将一个值为val的节点插入到链表中下标为index的节点之前。如果index等于链表的长度，那么该节点会被追加到链表的末尾。如果index比长度更大，该节点将 不会插入 到链表中。void deleteAtIndex(int index)如果下标有效，则删除链表中下标为index的节点。
示例
输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2); // 链表变为 1->2->3
myLinkedList.get(1); // 返回 2
myLinkedList.deleteAtIndex(1); // 现在，链表变为 1->3
myLinkedList.get(1); // 返回 3
题目链接
https://leetcode.cn/problems/design-linked-list/description/
解题思路
阵亡。没什么好的思路。属性只需要有大小和头节点就够了。自己写时不知道属性有哪些。
class MyLinkedList {
private ListNode head;
private int size;
public MyLinkedList() {
head = new ListNode(0);
size = 0;
}
public int get(int index) {
if (index < 0 || index >= size) {
return -1;
}
ListNode cur = head;
for (int i = 0; i <= index; i++) {
cur = cur.next;
}
return cur.val;
}
public void addAtHead(int val) {
addAtIndex(0, val);
}
public void addAtTail(int val) {
addAtIndex(size, val);
}
public void addAtIndex(int index, int val) {
if (index > size) {
return;
}
index = Math.max(0, index);
size++;
ListNode pred = head;
for (int i = 0; i < index; i++) {
pred = pred.next;
}
ListNode toAdd = new ListNode(val);
toAdd.next = pred.next;
pred.next = toAdd;
}
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) {
return;
}
size--;
ListNode pred = head;
for (int i = 0; i < index; i++) {
pred = pred.next;
}
pred.next = pred.next.next;
}
class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
}
LeetCode 206.反转链表
题目描述
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
题目链接
https://leetcode.cn/problems/reverse-linked-list/description/
解题思路
捋清关系还是很好解诀。
- 当前节点指向上一节点
prev = curcur = cur.next(第一步之前)
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode cur = head;
while (cur != null) {
ListNode node = cur.next;
cur.next = prev;
prev = cur;
cur = node;
}
return prev;
}
}
评论