站酷网页版,做企业免费网站,企业模板免费下载,网页设计教程多少钱一.LinkedList的方法
首先先看一下链表的方法#xff1a;
方法解释boolean add(E e)尾插void add(int index, E element)将 e 插入到 index 位置boolean addAll(Collection c)尾插 c 中的元素E remove(int index)删除 index 位置元素boolean remove(Object o)删除遇到的第一…一.LinkedList的方法
首先先看一下链表的方法
方法解释boolean add(E e)尾插void add(int index, E element)将 e 插入到 index 位置boolean addAll(Collection c)尾插 c 中的元素E remove(int index)删除 index 位置元素boolean remove(Object o)删除遇到的第一个 oE get(int index)获取下标 index 位置元素E set(int index, E element)将下标 index 位置元素设置为 elementvoid clear()清空boolean contains(Object o)判断 o 是否在线性表中int indexOf(Object o)返回第一个 o 所在下标int lastIndexOf(Object o)返回最后一个 o 的下标List subList(int fromIndex, int toIndex)截取部分 list
二.反转链表
题目对应LeetCode206. 反转链表
/*** 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(headnull || head.nextnull){return head;}ListNode prhead;ListNode curhead.next;ListNode pcur.next;while(cur!null){cur.nextpr;prcur;curp;if(p!null){pp.next;}}head.nextnull;return pr;}
}
思路从前往后将每一个节点的next改成其前一个节点。
定义三个ListNode变量指向三个节点cur指向的是当前要改变next的节点pr指向的是cur.next要指向的节点p是记录的作用如果cur的next变成指向前面了那么本来cur后面一个节点就丢失了无法完成反转。
三.快慢指针在链表的应用
不少题目的解题关键就在快慢指针。
首先是最经典的应用LeetCode876. 链表的中间结点
题目意思就是返回中间结点最笨的办法就是将链表遍历一遍看看有多少个结点然后再遍历出中间结点。这里使用快慢指针可以一步到位。
/*** 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 middleNode(ListNode head) {if(headnull){return head;}ListNode slowhead;ListNode fasthead;while(fast!null fast.next!null){slowslow.next;fastfast.next.next;}return slow;}
}
定义一个快指针和一个慢指针让快的一下走两步慢的一下走一步这样走到最后停止时slow刚好在中间结点上。
这个可以说是一个元问题很多链表的题目都有这道题快慢指针的影子。
像非常经典的回文链表问题CR 027. 回文链表用的都是快慢指针的思想。
四.相交链表
题目对应LeetCode160. 相交链表
这是题目的描述给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。 由例图可以看出在两个单链表相遇之后交点后面的结点都是相同的。先考虑最简单的情况如果两个链表的长度相同那么直接从头开始一个一个遍历知道找到交点。但是这个方法在双方长度不一时用不了。既然用不了那我们就借着这个思路改一下给短的链表补上不就行了换句话说链表从后往前对齐长链表前面多的那部分不可以有结点直接跳过即可这样问题就解决了。
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if(headAnull headBnull){return null;}int len0;int lb0;int la0;ListNode curheadA;while(cur!null){la;curcur.next;}curheadB;while(cur!null){lb;curcur.next;}ListNode lheadA;ListNode sheadB;lenla-lb;if(lalb){lheadB;sheadA;lenlb-la;}while(len!0){ll.next;len--;}while(l!s l!null s!null){ll.next;ss.next;}if(ls l!null){return l;}else{return null;}}
}
五.链表的环问题
1.是否存在环
题目对应LeetCode141. 环形链表
应用的也是快慢指针的思想这个就像在操场上跑步一样如果一快一慢而且还是闭环的话那么两个人一定会相遇。这个同理如果成环那么两个指针也是会相遇的。
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public boolean hasCycle(ListNode head) {if (head null) return false;ListNode slowhead;ListNode fasthead;while(fast!null fast.next!null){slowslow.next;fastfast.next.next;if(slowfast){return true;}}return false;}
}
2.返回入环后的第一个结点
题目对应LeetCode142. 环形链表 II
这个题里面有一个数学推导直接说结果起点到入环后第一个结点的距离快慢指针相遇的交点到入环后第一个结点的距离。
这个推导并不难就初中生水平大家可以自己试一下。
/*** 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 slowhead;ListNode fasthead;while(true){if(fastnull || fast.nextnull){return null;}slowslow.next;fastfast.next.next;if(fastslow){break;}}slowhead;while(slow!fast){slowslow.next;fastfast.next;}return slow;}
}
