LeetCode-链表操作题目

虚拟头指针，在当前head的前面建立一个虚拟头指针，然后哪怕当前的head的val等于提供的val也能进行统一操作

---

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 fakehead=new ListNode();//虚拟头指针指向head，然后做判断fakehead.next=head;ListNode current=fakehead;while(current.next!=null){//只要头指针的next不是空指针，等于val就删除，不等于就指向下一个指针if(current.next.val==val){current.next=current.next.next;}else{current=current.next;}}return fakehead.next;}
}

 建立虚拟头指针fakehead，用空构造函数建造就可以，将fakehead的next指向head

用current指向fakehead开始遍历链表，从head开始进行判断，cur的next的val值和提供的目标值一样就进行移除操作，否则移动指针指向cur的next指针。

---

707设计链表中等题

这道题非常考察链表的基本操作，沿用203题，为了进行单链表的统一操作，本题用虚拟头结点 

class MyLinkedList {//构建链表ListNodeclass ListNode{int val;ListNode next;ListNode(int val){this.val=val;}}//建立虚拟头结点private ListNode fakehead;//记录链表总长度private int nodelen;public MyLinkedList() {this.fakehead=new ListNode(0);this.nodelen=0;}public int get(int index) {//查找下标为index的valif(index<0 || index>=nodelen){return -1;}ListNode current=fakehead;//找到index+1for(int i=0;i<=index;i++){   current=current.next;}return current.val;}public void addAtHead(int val) {//虚拟头指针后面增加一个元素ListNode newnode=new ListNode(val);newnode.next=fakehead.next;fakehead.next=newnode;nodelen++;}public void addAtTail(int val) {//因为要在尾巴插入，所以要记录链表的总长度ListNode newnode=new ListNode(val);ListNode current=fakehead;while(current.next!=null){current=current.next;}//现在指向最后的元素了current.next=newnode;nodelen++;}public void addAtIndex(int index, int val) {if(index<0 || index>nodelen){return;}ListNode newnode=new ListNode(val);ListNode current=fakehead;//插入到index前面for(int i=0;i<index;i++){current=current.next;}newnode.next=current.next;current.next=newnode;        nodelen++;        }public void deleteAtIndex(int index) {if(index<0 ||index>=nodelen){return;}ListNode current=fakehead;for(int i=0;i<index;i++){current=current.next;}current.next=current.next.next;nodelen--;}
}

• 首先为了初始化链表，我们需要写一个链表类，然后定义两个成员变量fakehead（虚拟头指针）和nodelen（链表中元素的个数），初始化的时候fakehead定义为val为0的链表元素，nodelen为0
• 根据索引index去get一个元素的val值，首先要判断index是不是小于0或者大于等于nodelen（当前的元素值索引最大只能是nodelen-1），然后从i=0遍历到index+1就可以，因为是从虚拟头结点开始遍历的
• 在第一个元素添加很简单，就是虚拟头指针原来的next变为新添加元素的next，虚拟头指针的next指向新添加元素就可以了
• 在尾部添加元素，只需要一直遍历指针指向最后一个元素然后next设为新添加元素
• 给定索引index和val，在index元素的前面插入新元素，我们需要找到前置链表元素的位置，然后进行添加操作，用for循环遍历的时候，就需要遍历到index-1下标的元素位置

---

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 reverseList(ListNode head) {//一次翻转，用双指针，从头开始遍历ListNode pre=null;ListNode cur=head;//交换用ListNode temp=null;//前置指针先指向nullwhile(cur!=null){temp=cur.next;cur.next=pre;pre=cur;cur=temp;}return pre;}
}

双指针思想，设置pre为前置指针，让cur一直指向pre，就相当于反转了链表

注意：pre循环的时候要指向cur，而cur为了能指向本来的next，需要建立一个链表指针temp来保存

---

24两两交换链表中的节点 中等

虚拟头指针+两个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 swapPairs(ListNode head) {//建立一个虚拟头指针ListNode fake=new ListNode();fake.next=head;ListNode cur=fake;ListNode temp1=new ListNode();ListNode temp2=new ListNode();while(cur.next!=null && cur.next.next!=null){//满足交换条件temp1=cur.next;temp2=cur.next.next.next;//f-ccur.next=cur.next.next;//f-2-1cur.next.next=temp1;//f-2-1-3cur.next.next.next=temp2;cur=temp1;}return fake.next;        }
}

19删除链表的倒数第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 removeNthFromEnd(ListNode head, int n) {//虚拟头指针ListNode fake=new ListNode();fake.next=head;//设置双指针ListNode slow=fake;ListNode fast=fake;//先让fast移动到第n个位置for(int i=0;i<n;i++){fast=fast.next;}//再两个一起移动while(fast.next!=null){fast=fast.next;slow=slow.next;}//删除slow后面的节点slow.next=slow.next.next;return fake.next;}
}

 

用快慢双指针完成这个问题，虚拟头指针方便统一操作，slow的下一个指标对应的元素就是要删除的元素 

142环形链表

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {//检查有没有环，快慢指针，快指针移动两个元素，慢指针一次移动一个元素，如果有环一定会相遇ListNode fast=head;ListNode slow =head;while(fast!=null && fast.next!=null){slow=slow.next;fast=fast.next.next;if(slow==fast){//相遇了,记录相遇节点ListNode index1=slow;//设入口到head距离为x，环入口到相遇节点为y，相遇节点到入口的节点数是z//则有2(x+y)=x+y+n(y+z)等价于x=n(y+z)-y等价于x=(n-1)(y+Z)+z//由于n至少转了一圈以上，fast才能够追上slow，所以只要一个指针从head出发，一个指针从相遇节点出发，最终相遇的地方就是环的路口ListNode index0=head;while(index0!=index1){index0=index0.next;index1=index1.next;}return index0;}}return null;}
}

1.  快慢指针入手，快指针每次移动两个下标，慢指针每次移动一个，如果有环，必定相遇，由于快指针每次移动两个，所以while循环的条件是他现在和next都不为null
2. 如何判断出口，就要用数学公式进行判断，根据相遇的时候，快指针移动节点的个数是慢指针移动节点个数的二倍，列出等价公式，得到x=(n-1)(y+z)+z
3. 这说明从相遇节点出发无论快指针是走了一圈y+z的路程还是很多圈，最终都会和从head出发的指针相遇，而这个相遇的地点就是环的入口指针
4. xyz示意图