很久没有接触到链表，最近拉出来复习和总结下，并总结了一些常见的链表的题型。本文主要使用Java进行测试。
链表主要有四种：单链表、双向链表、循环链表和静态链表，其中静态链表类似于数组的实现方式，需要预先分配空间大小，这里主要介绍的是动态链表即单链表、双向链表和循环链表。
定义
单链表
public class SingleLinkList {
public int data; //数据域
public SingleLinkList next = null; //指向下一个节点
public SingleLinkList(int data) {
this.data = data;
}
public static void print(SingleLinkList singleLinkList) { // 从根节点打印数据
System.out.println(singleLinkList.data);
singleLinkList = singleLinkList.next;
if (singleLinkList != null) { //节点为空就不打印了记得跳出，否则NullPointException
print(singleLinkList);
}
}
}
双向链表
public class DoubleLinkList {
public int data; //数据域
public DoubleLinkList front = null; //指向上一个节点
public DoubleLinkList next = null; //指向下一个节点
public DoubleLinkList(int data) {
this.data = data;
}
public static void print(DoubleLinkList doubleLinkList) { //从根节点打印数据
System.out.println(doubleLinkList.data);
doubleLinkList = doubleLinkList.next;
if (doubleLinkList != null) {
print(doubleLinkList);
}
}
}
循环链表
public class CircularLinkList {
public int data; //数据域
public CircularLinkList next = null; //指向下一个节点
public static int count = 1; //跳出遍历链表的计数器
public CircularLinkList(int data) {
this.data = data;
}
public static void print(CircularLinkList circularLinkList, int limit) {
System.out.println(circularLinkList.data);
circularLinkList = circularLinkList.next;
if (count < limit) { //打印limit个数据
count ++;
print(circularLinkList, limit);
}
}
}
为了方便测试我们写个打印数据的方法，定义好这三种链表之后，我们先初始化并给定一些数据。
public class Solution {
public static void main(String[] args) {
Solution solution = new Solution();
int arr[] = {11, 22, 33, 44, 55, 66, 77, 88, 99};
SingleLinkList singleLinkListHead = new SingleLinkList(arr[0]); //头结点
solution.initSingleLinkList(singleLinkListHead, arr);
SingleLinkList.print(singleLinkListHead);
DoubleLinkList doubleLinkList = new DoubleLinkList(arr[0]); //头结点
solution.initDoubleLinkList(doubleLinkList, arr);
DoubleLinkList.print(doubleLinkList);
CircularLinkList circularLinkList = new CircularLinkList(arr[0]);//头结点
solution.initCircularLinkList(circularLinkList, arr);
CircularLinkList.print(circularLinkList, 20);
}
//初始化单链表
public void initSingleLinkList(SingleLinkList singleLinkList, int[] arr) {
for (int i = 1; i<arr.length; i++) {
if (singleLinkList.next == null) {
singleLinkList.next = new SingleLinkList(arr[i]);
}
singleLinkList = singleLinkList.next;
}
}
//初始化双向链表
public void initDoubleLinkList(DoubleLinkList doubleLinkList, int[] arr) {
for (int i = 1; i<arr.length; i++) {
if (doubleLinkList.next == null) {
doubleLinkList.next = new DoubleLinkList(arr[i]);
}
DoubleLinkList frontNodes = doubleLinkList;
doubleLinkList = doubleLinkList.next;
doubleLinkList.front = frontNodes;
}
}
//初始化环形链表
public void initCircularLinkList(CircularLinkList circularLinkList, int[] arr) {
CircularLinkList head = circularLinkList;// 记录下头结点
for (int i = 1; i<arr.length; i++) {
if (circularLinkList.next == null) {
circularLinkList.next = new CircularLinkList(arr[i]);
}
circularLinkList = circularLinkList.next;
}
circularLinkList.next = head; //尾节点指向头结点形成环
}
}
这就定义好了测试数据了~，其中环形链表我给定了limit参数，用于指定输出的数据个数。
常见题型
- 求单链表中结点的个数
- 将单链表反转
- 查找单链表中的倒数第K个结点（k > 0）
- 查找单链表的中间结点
- 从尾到头打印单链表
- 已知两个单链表head1和head2各自有序，把它们合并成一个链表依然有序
- 判断一个单链表中是否有环
- 判断两个单链表是否相交
- 求两个单链表相交的第一个节点
- 已知一个单链表中存在环，求进入环中的第一个节点
待续...
1. 求单链表中结点的个数
emmm...这题比较简单，遍历单链表然后计数就行了。
public int count(SingleLinkList head) {
if (head == null) {
return 0;
}
int length = 1;
while (head.next != null) {
head = head.next;
length++;
}
return length;
}
2. 将单链表反转
个人理解：就是让当前节点的next指向前一个节点，那么就需要建立一个临时节点用于存放前一个节点。举个栗子：
定义链表数据为[11, 22, 33, 44],cur表示当前节点
开始遍历该单链表...
cur.data=11时，此时该节点为原始链表的头节点即新链表的尾节点，所以cur.next=null;
cur.data=22时，我们目的是要让cur.next指向cur.data=11时的节点，所以需要建立临时节点用于保存cur.data=11时的节点
public SingleLinkList reverse(SingleLinkList head) {
if (head == null || head.next == null) {//没有头结点或者只有头结点的链表直接返回
return head;
}
SingleLinkList newSingLinkList = null;
while (head.next != null) {
SingleLinkList temp = head.next;//临时节点 用于存放下一个节点，遍历原始链表
head.next = newSingLinkList;//当前节点的下一个节点指向当前节点的前一个节点
newSingLinkList = head;//存放当前节点
head = temp;
}
head.next = newSingLinkList;
newSingLinkList = head;
return newSingLinkList;
}
方法有很多，我这里用了感觉比较好理解的方法...
3. 查找单链表中的倒数第K个结点（k > 0）
方法一：先求出单链表的长度n，然后再遍历到n-k就可以了。
方法二：在查找过程中，设置两个指针，让其中一个指针比另一个指针先前移k-1步，然后两个指针同时向后移动。循环直到下一个节点为NULL，另一个指针所指向的位置就是所要找到的位置。直接看代码
public SingleLinkList getSingleLinkListByK(int k, SingleLinkList head) {
SingleLinkList orginal = head;
int i = 0;
while (i<k-1) {
if (head== null) {
return null; //超出单链表的范围了，返回
}
head= head.next;
i++;
}
SingleLinkList tempSingleLinkList = head;//向后移动k-1步
while (tempSingleLinkList.next!=null) {
tempSingleLinkList = tempSingleLinkList.next;//同时移动
orginal = orginal.next;
}
return orginal;
}
4. 查找单链表的中间结点
设置两个新的链表指向头结点，第一个链表每次向后移动一位，第二个链表每次向后移动两位，当第二个链表的下一个节点指向为null时，第一个链表指的即是中间节点。
public SingleLinkList getMiddle(SingleLinkList head) {
if (head == null || head.next == null) {//如果只有头结点或者链表为空直接返回
return head;
}
SingleLinkList first = head;
SingleLinkList second = head;
while (second.next != null) {
first = first.next;
second = second.next;
if (second.next != null) {
second = second.next;
}
}
return first;
}
5. 从尾到头打印单链表
最直接的方式就是递归
public void print(SingleLinkList head) {
if (head == null) { //一定要有跳出递归的判断
return;
} else {
print(head.next);
System.out.println(head.data);
}
}
6. 已知两个单链表head1和head2各自有序，把它们合并成一个链表依然有序（从小到大）
归并排序算法，先确定头节点再开始比较两个链表的元素。
public SingleLinkList sort(SingleLinkList head1, SingleLinkList head2) {
SingleLinkList result;
if (head1 == null) {
return head2;
}
if (head2 == null) {
return head1;
}
if (head1.data < head2.data) {//初始化头节点
result = head1;
head1 = head1.next;
} else {
result = head2;
head2 = head2.next;
}
result.next = null;
SingleLinkList temp = result;
while (head1!= null && head2!= null) {
if (head1.data<head2.data) {
temp.next = head1;
head1 = head1.next;
temp = temp.next;
} else {
temp.next = head2;
head2 = head2.next;
temp = temp.next;
}
temp.next = null;
}
if (head1!= null) {
temp.next = head1;
} else {
temp.next = head2;
}
return result;
}
7. 判断一个单链表中是否有环
使用快慢指针方法，定义两个单链表指向头节点，快指针每次移动2个位置，慢指针每次移动1个位置，如果两个指针能够相遇，则说明该单链表有环。
public boolean annular(SingleLinkList head) {
SingleLinkList head1 = head;
SingleLinkList head2 = head;
while (head1.next != null && head2.next != null) {
head1 = head1.next;//慢指针
head2 = head2.next.next;//快指针
if (head1 == head2) {
return true;
}
}
return false;
}
8. 判断两个单链表是否相交
方法1：可以对每个节点进行hash，再遍历两个单链表，当存在hash值相同的节点时，说明两个单链表相交。
方法2：两个单链表相交，说明两个单链表的最后一个节点肯定相同，直接看代码。
public boolean intersect(SingleLinkList head1, SingleLinkList head2) {
if (head1 == null || head2 == null) {
return false;
}
SingleLinkList temp1 = head1;
SingleLinkList temp2 = head2;
while (temp1.next != null) {
temp1 = temp1.next;
}
while (temp2.next != null) {
temp2 = temp2.next;
}
return temp1 == temp2;
}
9. 求两个单链表相交的第一个节点
方法1：求出两个单链表的长度分别为len1,len2，先让长的单链表移动|len1-len2|步，再同时遍历两个单链表，遇到的第一个相同节点即交点。
方法2：已知两个单链表相交，可以让尾节点指向其中一个链表的头节点，这样就转化为一个有环单链表，题目就转化为求有环链表的入环点，和第10题一样。
10. 已知一个单链表中存在环，求进入环中的第一个节点
未完成。。待续。。
