一.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) | 删除遇到的第一个 o |
E get(int index) | 获取下标 index 位置元素 |
E set(int index, E element) | 将下标 index 位置元素设置为 element |
void clear() | 清空 |
boolean contains(Object o) | 判断 o 是否在线性表中 |
int indexOf(Object o) | 返回第一个 o 所在下标 |
int lastIndexOf(Object o) | 返回最后一个 o 的下标 |
List subList(int fromIndex, int toIndex) | 截取部分 list |
二.反转链表
题目对应LeetCode: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) {
if(head==null || head.next==null){
return head;
}
ListNode pr=head;
ListNode cur=head.next;
ListNode p=cur.next;
while(cur!=null){
cur.next=pr;
pr=cur;
cur=p;
if(p!=null){
p=p.next;
}
}
head.next=null;
return pr;
}
}
思路:从前往后将每一个节点的next改成其前一个节点。
定义三个ListNode变量指向三个节点,cur指向的是当前要改变next的节点,pr指向的是cur.next要指向的节点,p是记录的作用,如果cur的next变成指向前面了,那么本来cur后面一个节点就丢失了,无法完成反转。
三.快慢指针在链表的应用
不少题目的解题关键就在快慢指针。
首先是最经典的应用:LeetCode:876. 链表的中间结点
题目意思就是返回中间结点,最笨的办法就是将链表遍历一遍,看看有多少个结点,然后再遍历出中间结点。这里使用快慢指针可以一步到位。
/**
* 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(head==null){
return head;
}
ListNode slow=head;
ListNode fast=head;
while(fast!=null && fast.next!=null){
slow=slow.next;
fast=fast.next.next;
}
return slow;
}
}
定义一个快指针和一个慢指针,让快的一下走两步,慢的一下走一步,这样走到最后停止时,slow刚好在中间结点上。
这个可以说是一个元问题,很多链表的题目都有这道题快慢指针的影子。
像非常经典的回文链表问题:CR 027. 回文链表,用的都是快慢指针的思想。
四.相交链表
题目对应LeetCode:160. 相交链表
这是题目的描述:给你两个单链表的头节点 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(headA==null && headB==null){
return null;
}
int len=0;
int lb=0;
int la=0;
ListNode cur=headA;
while(cur!=null){
la++;
cur=cur.next;
}
cur=headB;
while(cur!=null){
lb++;
cur=cur.next;
}
ListNode l=headA;
ListNode s=headB;
len=la-lb;
if(la<lb){
l=headB;
s=headA;
len=lb-la;
}
while(len!=0){
l=l.next;
len--;
}
while(l!=s && l!=null && s!=null){
l=l.next;
s=s.next;
}
if(l==s && l!=null){
return l;
}else{
return null;
}
}
}
五.链表的环问题
1.是否存在环
题目对应LeetCode:141. 环形链表
应用的也是快慢指针的思想,这个就像在操场上跑步一样,如果一快一慢,而且还是闭环的话,那么两个人一定会相遇。这个同理,如果成环,那么两个指针也是会相遇的。
/**
* 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 slow=head;
ListNode fast=head;
while(fast!=null && fast.next!=null){
slow=slow.next;
fast=fast.next.next;
if(slow==fast){
return true;
}
}
return false;
}
}
2.返回入环后的第一个结点
题目对应LeetCode:142. 环形链表 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 slow=head;
ListNode fast=head;
while(true){
if(fast==null || fast.next==null){
return null;
}
slow=slow.next;
fast=fast.next.next;
if(fast==slow){
break;
}
}
slow=head;
while(slow!=fast){
slow=slow.next;
fast=fast.next;
}
return slow;
}
}