LeetCode分类刷题----链表篇
阿里云国际版折扣https://www.yundadi.com |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
链表
链表
1.移除链表元素
203.移除链表元素
给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val == val 的节点并返回 新的头节点 。
示例 1
输入head = [1,2,6,3,4,5,6], val = 6
输出[1,2,3,4,5]
思路1原链表删除
要考虑两种情况
如果要删除的元素是头节点那么需要将头节点指向下一个。如果头节点不是目标元素。要想删除一个节点必须知道这个节点的上一个节点然后跳跃删除。
public ListNode removeElements1(ListNode head, int val) {
while(head!=null&&head.val==val) {
head=head.next;
}
ListNode cur=head;
while(cur!=null) {
while(cur.next!=null&&cur.next.val==val) {
cur.next=cur.next.next;
}
cur=cur.next;
}
return head;
}
思路2虚拟头节点
为链表新建一个头节点这样就不用考虑头节点是不是要删除的元素了直接进行跳跃删除。
public ListNode removeElements(ListNode head, int val) {
if(head==null) {
return head;
}
ListNode dummy=new ListNode(-1,head);
ListNode pre=dummy;
ListNode cur=head;
while(cur!=null) {
if(cur.val==val) {
pre.next=cur.next;
}else {
pre=cur;
}
cur=cur.next;
}
return dummy.next;
}
707.设计链表
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性val 和 next。val 是当前节点的值next 是指向下一个节点的指针/引用。如果要使用双向链表则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能
get(index)获取链表中第 index 个节点的值。如果索引无效则返回-1。
addAtHead(val)在链表的第一个元素之前添加一个值为 val 的节点。插入后新节点将成为链表的第一个节点。
addAtTail(val)将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度则该节点将附加到链表的末尾。如果 index 大于链表长度则不会插入节点。如果index小于0则在头部插入节点。
deleteAtIndex(index)如果索引 index 有效则删除链表中的第 index 个节点。
思路
这道题实现的功能就比较多了要注意控制节点的位置时要新声明一个节点不能用head来操作否则链表位置会乱套。思想是挺简单的但是实现起来还是有很多坑的。
class ListNode { //定义一个链表结构包括数值域指针域
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
public class MyLinkedList {
int size;
ListNode head;
public MyLinkedList() {//链表初始化注意这里声明了一个头节点和没有头节点的操作就大不相同
head = new ListNode(0);
size = 0;
}
public int get(int index) {
ListNode cur = head; //遍历位置信息时要新声明一个节点不能直接操作head
if (index < 0 || index > size - 1) {
return -1;
}
while (index != 0) {
cur = cur.next;
index--;
}
return cur.next.val;
}
public void addAtHead(int val) { //在头部添加一个节点
ListNode newNode = new ListNode(val);
newNode.next = head.next;
head.next = newNode;
size++;
}
public void addAtTail(int val) { //在尾部添加一个节点只要按顺序找到最后一个指针就行了
ListNode newNode = new ListNode(val);
ListNode cur = head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = newNode;
size++;
}
public void addAtIndex(int index, int val) {
if (index > size) {
return;
}
ListNode newNode = new ListNode(val);
if (index <= 0) { //在头节点增加
newNode.next = head.next;
head.next = newNode;
size++;
} else {
ListNode cur = head;
while (index >= 1) { //在其他的位置增加记好数就ok了
cur = cur.next;
index--;
}
newNode.next = cur.next;
cur.next = newNode;
size++;
}
}
public void deleteAtIndex(int index) {
ListNode cur = head;
if (index < 0 || index > size - 1) {
return;
}
if (index == 0) {
head = head.next;
}
while (index >= 1) {
cur = cur.next;
index--;
}
cur.next = cur.next.next; //找到目标位置直接跳步删除即可
size--;
}
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(2);
// myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(0, 1);
System.out.println(myLinkedList.get(1));
// myLinkedList.deleteAtIndex(1);
// System.out.println(myLinkedList.get(1));
}
}
2.反转链表
206.反转链表
给你单链表的头节点 head 请你反转链表并返回反转后的链表。
示例 1
输入head = [1,2,3,4,5]
输出[5,4,3,2,1]
思路1正常反转
先保存了头指针的下一个节点然后让头指针指向pre然后pre和头指针都往后移。第二次看这个链表反转有很大的收获之前我一直以为反转是要重新建一条链表现在再看知识需要把head.next的指针指向前边就可以了。
class Solution {
public ListNode reverseList(ListNode head) {
ListNode next=null;
ListNode pre=null;
while(head!=null){
next=head.next;
head.next=pre;
pre=head;
head=next;
}
return pre;
}
}
思路2递归反转
思路和正常反转一样只不过是套了一个递归函数把后边那个语句换成递归函数就可以了。
public ListNode reverseList(ListNode head) {
return reverse(head , null);
}
public ListNode reverse(ListNode head,ListNode pre) {
if(head==null) {
return pre ;
}
ListNode next=null;
next=head.next;
head.next=pre;
return reverse(next,head);
}
3.两两交换链表中的节点
24.两两交换链表中的节点
思路
判断好结束条件然后申请两个临时指针分别保存好下面两个节点的元素然后交换即可。
public ListNode swapPairs(ListNode head) {
ListNode dummy=new ListNode(0);//创建一个虚拟头节点
dummy.next=head;
ListNode cur=dummy; //进行操作的指针
ListNode temp1; //两个临时指针
ListNode temp2;
while(cur.next!=null&&cur.next.next!=null) {//判断结束条件链表节点是奇数还是偶数的情况都包含进去了
temp1=cur.next;//保存下一个节点的指针
temp2=cur.next.next;//保存第二个节点的指针
cur.next=temp2;
temp1.next=temp2.next;
temp2.next=temp1;
cur=temp1; //移动cur指针保证它在要操作的节点的前一个节点
}
return dummy.next;
}
4.删除链表中的倒数第N个节点
19.删除链表的倒数第N个节点
思路
设立两个快慢指针先让快指针走n+步当快指针指向链表尾节点的时候此时慢指针恰好走到要删除节点的前一个节点此时对慢指针进行删除即可。设立虚拟头节点的好处是避免了空指针异常。
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy=new ListNode(0);
dummy.next=head;
//设立快慢指针先让快指针移动n+1不然后快慢指针同时移动
ListNode fast=dummy;
ListNode slow=dummy;
n++;
while(n--!=0&&fast!=null) {
fast=fast.next;
}
while(fast!=null) {
fast=fast.next;
slow=slow.next;
}
slow.next=slow.next.next;
return dummy.next;
}
5.链表相交
07.链表相交
思路
两个指针当着两个指针走向尽头时然后转向另一个链表的头节点直到这两个链表相遇因为这两个节点都走了同样的长度。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA==null||headB==null) {
return null;
}
ListNode pA=headA;
ListNode pB=headB;
while(pA!=pB) {
pA=pA==null?headB:pA.next;
pB=pB==null?headA:pB.next;
}
return pA;
}
6.环形链表
141.环形链表
思路
一个快指针一个慢指针当快指针和慢指针相遇的话一定会有环。
public boolean hasCycle(ListNode head) {
if(head==null) {
return false;
}
ListNode slow=head;
ListNode fast=head;
if(head.next!=null) {
fast=head.next;
}
while(fast.next!=null&&fast.next.next!=null) {
if(fast==slow) {
return true;
}
slow=slow.next;
fast=fast.next.next;
}
return false;
}
142.环形链表II
思路
和第一个不同的是这个要返回环形链表的交点了。
设头节点到成环节点的距离为x设成环节点到相遇节点的距离为y设相遇节点到成环节点的距离为z。慢指针移动的距离为x+y.快指针走的节点数为x+n(y+z)。
因为快指针速度是慢指针的二倍所以有2(x+y)=x+n(y+z)
整理得x=n(y+z)-y=(n-1)(y+z)+z。
当n=1的时候有x=z。当n不等于1的时候说明快指针在环里移动了好几圈也不影响题目
此时代表index1指针在环里多转了n-1圈才遇到的index2相遇节点也是入环的初始位置。
public ListNode detectCycle(ListNode head) {
if(head==null) {
return null;
}
ListNode slow=head;
ListNode fast=head;
while(fast!=null&&fast.next!=null) {
slow=slow.next;
fast=fast.next.next;
if(fast==slow) {
ListNode index1=fast;
ListNode index2=head;
while(index1!=index2) {
index1=index1.next;
index2=index2.next;
}
return index1;
}
}
return null;
}