【LeetCode刷题】链表篇

203. 移除链表元素

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

707. 设计链表

class Node{public int data;public Node next;public Node(){;}public Node(int val,Node next){this.data=val;this.next=next;}
}
class MyLinkedList {public int size=0;public Node head;public MyLinkedList() {head=new Node(0,null);size=0;}public int get(int index) {if(index>=size||index<0)return -1;Node ptr=head;for(int i=0;i<=index;i++){ptr=ptr.next;}return ptr.data;}public void addAtHead(int val) {Node newHead=new Node(val,head.next);head.next=newHead;size++;}public void addAtTail(int val) {Node ptr=head;while(ptr.next!=null){ptr=ptr.next;}Node tail=new Node(val,null);ptr.next=tail;size++;}public void addAtIndex(int index, int val) {Node pre=head;if(index==size){addAtTail(val);return ;}if(index>size)return ;if(index<0)index=0;for(int i=0;i<index;i++){pre=pre.next;}Node node=new Node(val,pre.next);pre.next=node;size++;}public void deleteAtIndex(int index) {if(index>=size)return;Node pre=head;for(int i=0;i<index;i++){pre=pre.next;}pre.next=pre.next.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);*/

206.反转链表

思路一：顺序遍历原有链表，使用头插法建立新链表即为反转后的链表。时间复杂度O（n）空间复杂度也为O（n）

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

思路二：原地翻转，ptr用于遍历链表，pre指向在原链表中的前驱，temp用于存储ptr的后驱，最后pre所指就是反转后的头节点

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