网站建设平台哪个好_3d游戏制作软件_网站收录服务_外包

203. 移除链表元素

leetcode题目地址

思路二

创建虚节点作为头结点指向原链表，对链表中的目标元素进行删除，最后返回虚节点的下一个结点。

时间复杂度： $O(n)$
空间复杂度： $O(1)$

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

思路二

创建虚节点作为一条新链表的头结点，next为空。从原链表中寻找不是目标值的结点，接到新链表尾。

时间复杂度： $O(n)$
空间复杂度： $O(1)$

/*** 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 newHead = new ListNode(-1, null), q = newHead;ListNode p = head, pre = null;while(p != null){if(p.val != val){// 记录节点地址pre = p;// 指针后移（防止修改next断链）p = p.next;// 将该节点接入新链表pre.next = q.next;q.next = pre;q = pre;}else{p = p.next;}}return newHead.next;}
}

707. 设计链表

leetcode题目地址

维护头指针、尾指针以及链表长度三个属性，这样可以避免在尾部插入元素时遍历整个链表。

时间复杂度： 涉及index的操作为 $O(index)$, 其余操作为$O(1)$
空间复杂度： $O(n)$

// java
class Node{int val;Node next;public Node(){next = null;}public Node(int val){this.val = val;next = null;}
}class MyLinkedList {private Node head;private Node tail;private int length;public MyLinkedList() {this.head = new Node();this.tail = head;this.length = 0;}public int get(int index) {if(index < 0 || index >= this.length) return -1;Node p = head.next;while(index--!=0) p = p.next;return p.val;}   public void addAtHead(int val) {Node newNode = new Node(val);newNode.next = this.head.next;this.head.next = newNode;if(tail.equals(head)) tail = newNode;this.length++;}public void addAtTail(int val) {Node newNode = new Node(val);newNode.next = this.tail.next;this.tail.next = newNode;tail = newNode;this.length++;}public void addAtIndex(int index, int val) {if(index < 0 || index > this.length) return;if(index == this.length) this.addAtTail(val);else{Node newNode = new Node(val);Node pre = head;while(index--!=0){pre = pre.next;}newNode.next = pre.next;pre.next = newNode;this.length++;}}public void deleteAtIndex(int index) {if(index < 0 || index >= this.length) return;Node pre = head;while(index--!=0){pre = pre.next;}if(this.tail.equals(pre.next)){tail = pre;}pre.next = pre.next.next;this.length--;}
}/*** 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. 反转链表

leetcode题目地址

使用头插法实现单链表就地逆置。

时间复杂度： $O(n)$
空间复杂度： $O(1)$

// java
/*** 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 dummyHead = new ListNode(0, null);ListNode p = head, cur=null;while( p != null){cur = p;p = p.next;cur.next = dummyHead.next;dummyHead.next = cur;} return dummyHead.next;}
}