203. 移除链表元素 707 设计链表 206 反转链表

时间:2023-01-14 07:57:14


203. 移除链表元素

203. 移除链表元素 707 设计链表 206 反转链表


此题需要哨兵节点注意边界即可,很简单不多概述。

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

203. 移除链表元素 707 设计链表 206 反转链表

707. 设计链表

203. 移除链表元素 707 设计链表 206 反转链表


熟悉链表的删除和增加此题不难,我忽略了size++,浪费了半天时间

class MyLinkedList {
int size;
ListNode headA;
public MyLinkedList() {
size = 0;
headA = new ListNode(-1,null);
}

public int get(int index) {

if(index < 0 || index >= size){
return -1;
}else{
ListNode l1 = headA;
while(index >= 0){
l1 = l1.next;
index--;
}
return l1.val;
}
}

public void addAtHead(int val) {
addAtIndex(0,val);

}

public void addAtTail(int val) {
ListNode l1 = headA;
ListNode temp = new ListNode(val,null);
while(l1.next != null){
l1 = l1.next;
}
l1.next = temp;
size++;
}

public void addAtIndex(int index, int val) {
if(index > size) return;
if(index == size){
addAtTail(val);
return;
}
ListNode temp = new ListNode(val,null);
if(index <= 0){
temp.next = headA.next;
headA.next = temp;
}else{
ListNode l1 = headA;
while(index > 0){
l1 = l1.next;
index--;
}
temp.next = l1.next;
l1.next = temp;
}
size++;
}

public void deleteAtIndex(int index) {
ListNode l1 = headA;
ListNode l2 = headA.next;
if(index >= 0 && index < size){
while(index > 0){
index--;
l1 = l2;
l2 = l2.next;
}
l1.next = l2.next;
size--;
}

}
}

/**
* 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);
*/

203. 移除链表元素 707 设计链表 206 反转链表

206 反转链表

203. 移除链表元素 707 设计链表 206 反转链表


203. 移除链表元素 707 设计链表 206 反转链表


递归法,剑指offer原题

/**
* 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 headA = reverseList(head.next);
head.next.next = head;
head.next = null;
return headA;
}

}

203. 移除链表元素 707 设计链表 206 反转链表