代码随想录训练营二刷第三天 | 203.移除链表元素 707.设计链表 206.反转链表

一、203.移除链表元素

题目链接：https://leetcode.cn/problems/remove-linked-list-elements/
思路：使用虚拟头结点，两个指针，一个是遍历指针，一个是指向当前位置的上一个位置

/*** 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 null;ListNode node = new ListNode(-1, head);ListNode pre = node, cur = head;while (cur != null) {if (cur.val == val) {pre.next = cur.next;}else {pre = cur;}cur = cur.next;}return node.next;}
}

一、707.设计链表

题目链接：https://leetcode.cn/problems/design-linked-list/
思路：需要定义单独一个链表对象，然后用MyLinkedList来操作定义的链表对象，默认初始化一个虚拟头结点。

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 MyLinkedList {int len ;ListNode head;public MyLinkedList() {len = 0;head = new ListNode(-1);}public int get(int index) {if (index < 0 || index >= len) {return -1;}int i = 0;ListNode p = head;while (i <= index) {i++;p = p.next;}return p.val;}public void addAtHead(int val) {addAtIndex(0, val);}public void addAtTail(int val) {addAtIndex(len, val);}public void addAtIndex(int index, int val) {if (index > len) {return;}if (index < 0) {index = 0;}int i = 0;ListNode p = head;while (i < index) {i++;p = p.next;}p.next = new ListNode(val, p.next);len++;}public void deleteAtIndex(int index) {if (index < 0 || index >= len) {return;}ListNode pre = head, cur = head.next;int i = 0;while (i < index) {i++;pre = cur;cur = cur.next;}pre.next = cur.next;len--;}
}/*** Your MyLinkedList object will be instantiated and called as such:* MyLinkedList obj = new MyLinkedList();* int param_1 = obj.get(index);* obj.addAtHead(val);* obj.addAtTail(val);* obj.addAtIndex(index,val);* obj.deleteAtIndex(index);*/

一、206.反转链表

题目链接：https://leetcode.cn/problems/reverse-linked-list/
思路：很经典的题目，每次操作前用一个临时指针保存cur的next，然后让cur 指向pre，只有pre跟进一步，pre=cur，然后cur=temp

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