算法训练(leetcode)二刷第三天 | 203. 移除链表元素、707. 设计链表、206. 反转链表
刷题记录
- 203. 移除链表元素
- 思路二
- 思路二
- 707. 设计链表
- 206. 反转链表
203. 移除链表元素
leetcode题目地址
思路二
创建虚节点作为头结点指向原链表,对链表中的目标元素进行删除,最后返回虚节点的下一个结点。
时间复杂度:
O
(
n
)
O(n)
O(n)
空间复杂度:
O
(
1
)
O(1)
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(n)
O(n)
空间复杂度:
O
(
1
)
O(1)
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
(
i
n
d
e
x
)
O(index)
O(index), 其余操作为
O
(
1
)
O(1)
O(1)
空间复杂度:
O
(
n
)
O(n)
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(n)
O(n)
空间复杂度:
O
(
1
)
O(1)
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;
}
}