【Java数据结构】 链表

【本节目标】

1. ArrayList 的缺陷

2. 链表

3. 链表相关 oj题目

一. ArrayList的缺陷

        上节课已经熟悉了ArrayList 的使用，并且进行了简单模拟实现。通过源码知道， ArrayList 底层使用数组来存储元素：

public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{// ...
// 默认容量是10private static final int DEFAULT_CAPACITY = 10;//...
// 数组：用来存储元素transient Object[] elementData; // non-private to simplify nested class access// 有效元素个数private int size;public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}}
// ...
}

        由于其底层是一段连续空间，当在 ArrayList 任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后 搬移，时间复杂度为 O(n) ，效率比较低，因此 ArrayList 不适合做任意位置插入和删除比较多的场景 。因此： java集合中又引入了LinkedList ，即链表结构。

二. 链表

1 链表的概念及结构

        链表是一种物理存储结构上非连续 存储结构，数据元素的 逻辑顺序 是通过链表中的 引用链接 次序实现的 。

实际中链表的结构非常多样，以下情况组合起来就有 8 种链表结构：

单向------双向

循环------ 非循环

带头------ 不带头

（1）  单向或者双向

（2）  带头或者不带头

（3） 循环或者非循环

虽然有这么多的链表的结构，但是我们重点掌握两种 :

• 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多

• 无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

2 链表的实现

1、无头单向非循环链表实现

链表的基本表示：

static class ListNode{public int val;public ListNode next;public ListNode(int data){this.val=data;}}public ListNode head;//链表的头

对应的方法：

public interface IList {//头插法public void addFirst(int data);//尾插法public void addLast(int data);//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中public boolean contains(int key);//删除第一次出现关键字为key的节点public void remove(int key);//删除所有值为key的节点public void removeAllKey(int key);//得到单链表的长度public int size();public void clear() ;public void display();
}

实现对应的方法: 

(1)display

public void display() {ListNode cur=head;//不能改变头的引用while(cur!=null){System.out.print(cur.val+" ");cur=cur.next;}}

(2)size

  public int size() {int len=0;ListNode cur=head;while (cur!=null){len++;cur=cur.next;}return len;}

(3)contains

    public boolean contains(int key) {ListNode cur=new ListNode(key);while(cur!=null){if(cur.val==key){return true;}cur=cur.next;}return false;}

 (4)addFirst/头插

  public void addFirst(int data) {ListNode listNode=new ListNode(data);//该节点是新的头节点listNode.next=head;head=listNode;}

 (5)addFirst/尾插

public void addLast(int data) {ListNode listNode=new ListNode(data);if(head==null){head=listNode;return;}ListNode cur=head;while(cur.next!=null){cur=cur.next;}cur.next=listNode;}

 (6)addIndex/任意位置插

public void addIndex(int index, int data) {int len=size();if (index<0||index>len){new IndexOutOfBoundary("index输入有误");return;}if(index==0){addFirst(data);return;}if(index==len){addLast(data);return;}int curLen=0;ListNode cur=head;ListNode listNode=new ListNode(data);while(curLen<index-1){curLen++;cur=cur.next;}listNode.next=cur.next;cur.next=listNode;}

   (7)remove

    public void remove(int key) {if(head==null){//链表为空return;}if(head.val==key){//删除的位置在头节点head=head.next;return;}ListNode pre=findPreNodeOfKey(key);if(pre!=null){ListNode del=pre.next;//找到需要删除的节点pre.next=del.next;}}private  ListNode findPreNodeOfKey(int key){ListNode cur=head;while(cur.next!=null){//最后一个节点也已经判断过了if (cur.next.val==key){return cur;}cur=cur.next;}return null;}

  (8)removeAllKey

 public void removeAllKey(int key) {if(head==null){return;}ListNode prev=head;ListNode cur=head.next;while(cur!=null){if(cur.val==key){prev.next=cur.next;cur= cur.next;}else {prev=prev.next;cur= cur.next;}}//把前面的除头节点之外的都删完之后删除头节点if (head.val==key){head=head.next;}}

  (9)clear

   public void clear() {ListNode cur=head;while (cur!=null){ListNode curN=cur.next;cur.next=null;//基本数据类型的val不需要回收cur=curN;}}

三.链表相关题目

1. 删除链表中等于给定值 val 的所有节点。   

/*** 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 data){if(head==null){return head;}ListNode prev=head;ListNode cur=head.next;while(cur!=null){if(cur.val==data){prev.next=cur.next;cur=cur.next;}else{prev=prev.next;cur=cur.next;}}if(head.val==data){head=head.next;}return head;}}

2. 反转一个单链表。

可以采取不停的进行头插，将后面的节点不停的插到前面 

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

3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

/*** 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;}
}

4. 输入一个链表，输出该链表中倒数第 k 个结点。

import java.util.*;/** public class ListNode {*   int val;*   ListNode next = null;*   public ListNode(int val) {*     this.val = val;*   }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pHead ListNode类 * @param k int整型 * @return ListNode类*/public ListNode FindKthToTail (ListNode pHead, int k) {int count=0;ListNode f=pHead;while(f!=null){count++;f=f.next;}if(k>count||k<=0){return null;}if(pHead==null){return pHead;}// write code hereListNode prev=pHead;ListNode cur=pHead;while((k-1)!=0){cur=cur.next;k--;}while(cur!=null&&cur.next!=null){prev=prev.next;cur=cur.next;}return prev;}
}

经过重新调整，除了计算出有多少元素，防止多删除之外，可以在快指针走的时候就进行判断，走太多就会超过限制，那么就会走到空指针出，也可以判断

while((k-1)!=0){cur=cur.next;k--;if(cur==null){return null;}}

5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

/*** 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 mergeTwoLists(ListNode list1, ListNode list2) {ListNode cur1=list1;ListNode cur2=list2;ListNode newHead=new ListNode();ListNode tmp=newHead;if(cur1==null&&cur2==null){return null;}while(cur1!=null&&cur2!=null){if(cur1.val<=cur2.val){tmp.next=cur1;cur1=cur1.next;tmp=tmp.next;}else{tmp.next=cur2;cur2=cur2.next;tmp=tmp.next;}}if(cur1!=null){tmp.next=cur1;cur1=cur1.next;tmp=tmp.next;}if(cur2!=null){tmp.next=cur2;cur2=cur2.next;tmp=tmp.next;}return newHead.next;}
}

6. 编写代码，以给定值 x 为基准将链表分割成两部分，所有小于 x 的结点排在大于或等于 x 的结点之前 。

• 利用两个链表，一个存放小于x的值，一个存放大于x的值
• 要注意的是最后的判断条件，可能不存在小于x的，则直接返回第二个链表；且如果第二个链表不为空，链表结尾要置空，防止越界。

import java.util.*;/*
public class ListNode {int val;ListNode next = null;ListNode() { }ListNode(int val) {this.val = val;}
}*/
public class Partition {public ListNode partition(ListNode pHead, int x) {// write code hereListNode list1start=null;ListNode list1end=null;ListNode list2start=null;ListNode list2end=null;while(pHead!=null){if(pHead.val<x){if(list1start==null){list1start=list1end=pHead;}else{list1end.next=pHead;list1end=list1end.next;}}else{if(list2start==null){list2start=list2end=pHead;}else{list2end.next=pHead;list2end=list2end.next;   }  }pHead=pHead.next;}if(list1start==null){return list2start;}list1end.next=list2start;if(list2start!=null){list2end.next=null;}return list1start;}
}

7. 链表的回文结构。

使用快慢指针，找到中间节点，将中间节点之后的结点进行反转。然后分别向中间比较。

import java.util.*;/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class PalindromeList {public boolean chkPalindrome(ListNode head) {// write code hereif(head == null) return true;ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}//slow 指向的位置 就是中间节点//2.进行翻转ListNode cur = slow.next;while (cur != null) {ListNode curN = cur.next;cur.next = slow;slow = cur;cur = curN;}//3.判断回文while (head != slow) {if(head.val != slow.val) {return false;}if(head.next == slow) {return true;}head = head.next;slow = slow.next;}return true;}
}

8. 输入两个链表，找出它们的第一个公共结点。

分别去求两个链表的长度，让长的链表去走两个链表的差值

/*** 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) {ListNode pl=headA;ListNode ps=headB;int len1=0;int len2=0;while(pl!=null){pl=pl.next;len1++;}while(ps!=null){ps=ps.next;len2++;}pl=headA;ps=headB;int k=len1-len2;if(k<0){pl=headB;ps=headA;k=0-k;} while(k!=0){pl=pl.next;k--;}while(pl!=ps){pl=pl.next;ps=ps.next;}//若两个链表不相交if(pl==null){return null;}return pl;}
}

9. 给定一个链表，判断链表中是否有环。

/*** 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) {ListNode slow=head;ListNode fast=head;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;if(fast==slow){return true;}}return false;}
}

【思路】

        快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。比如：陪女朋友到操作跑步减肥。

【扩展问题】

• 为什么快指针每次走两步，慢指针走一步可以？

        假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在慢指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。

• 快指针一次走3步，走4步，...n步行吗？

10. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回  NULL 

起点到入口点的距离和相遇点到入口点的距离相等

此时slow从开头处开始走，fast从相遇点开始走，以相同的速度运动，相遇时则为相交点

/*** 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(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;if(slow==fast){break;}}if(fast==null||fast.next==null){return null;}slow=head;while(slow!=fast){fast=fast.next;slow=slow.next;}return slow;    }
}

结论

让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针 都是每次均走一步，最终肯定会在入口点的位置相遇 。

证明