总结提高，与君共勉
概述、
数据结构与算法亘古不变的主题，链表也是面试常考的问题，特别是手写代码常常出现，将从以下方面做个小结
【链表个数】
【反转链表-循环】
【反转链表-递归】
【查找链表倒数第K个节点】
【查找链表中间节点】
【判断链表是否有环】
【从尾到头打印单链表-递归】
【从尾到头打印单链表-栈】
【由小到大合并有序单链表-循环】
【由小到大合并有序单链表-递归】
通常在java中这样定义单链表结构
<span style="font-family:Microsoft YaHei;font-size:14px;">class Node{
int value;
Node next;
public Node(int n){
this.value = n;
this.next = null;
}
}
</span>
1、链表个数
这个比较简单，不再赘述
<span style="font-family:Microsoft YaHei;font-size:14px;"> // 求单链表的结点个数
public int getListLen(Node head) {
int len = 0;
while (head != null) {
len++;
head = head.next;
}
return len;
}</span>
2、反转链表-循环
采用双指针，主要是4行代码，其中2,3俩行完成指针反转，1,4主要是保持head往下指
<span style="font-family:Microsoft YaHei;font-size:14px;">// 反转单链表(循环)
public Node reverseList(Node head) {
// 安全性检查
if (head == null || head.next == null)
return head;
Node pre = null;
Node temp = null;
while (head != null) {
// 以下1234均指以下四行代码
temp = head.next;// 与第4行对应完成头结点移动
head.next = pre;// 与第3行对应完成反转
pre = head;// 与第2行对应完成反转
head = temp;// 与第1行对应完成头结点移动
}
return pre;
}</span>
3、反转链表-递归
<span style="font-family:Microsoft YaHei;font-size:14px;">// 将单链表反转,递归
public static Node reverseListRec(Node head) {
if (head == null || head.next == null)
return head;
Node reHead = reverseListRec(head.next);
head.next.next = head;
head.next = null;
return reHead;
}</span>
4、查找链表倒数第K个节点
双指针法，不多解释
<span style="font-family:Microsoft YaHei;font-size:14px;">// 查找单链表倒数第K个结点 双指针法
public Node reKNode(Node head, int k) {
if (head == null)
return head;
int len = getListLen(head);
if (k > len)
return null;
Node targetK = head;
Node nextK = head;
// 先走到K个位置
for (int i = 0; i < k; i++) {
nextK = nextK.next;
}
// 再和头结点一起走，nextk走到结尾，此时targetk为倒数第K个节点
while (nextK != null) {
nextK = nextK.next;
targetK = targetK.next;
}
return targetK;
}</span>
5、查找链表中间节点
快慢指针，不多解释
<span style="font-family:Microsoft YaHei;font-size:14px;">public Node getMid(Node head) {
// 类似的快慢指针法
// 安全性检查
if (head == null || head.next == null)
return head;
Node target = head;
Node temp = head;
while (temp != null && temp.next != null) {
target = target.next;
temp = temp.next.next;
}
return target;
}</span>
6、判断链表是否有环
主要还是快慢指针，如果快的指针能够追上慢指针则有环
<span style="font-family:Microsoft YaHei;font-size:14px;">// 判断一个单链表中是否有环,快慢指针
public boolean hasCycle(Node head) {
boolean flag = false;
Node p1 = head;
Node p2 = head;
while (p1 != null && p2 != null) {
p1 = p1.next;
p2 = p2.next.next;
if (p2 == p1) {
flag = true;
break;
}
}
return flag;
}</span>
7、从尾到头打印单链表-递归
<span style="font-family:Microsoft YaHei;font-size:14px;">// 从尾到头打印单链表(递归)
public void reList1(Node head) {
// 安全性检查
if (head == null)
return;
else {
reList1(head.next);
System.out.println(head.value);
}
}</span>
8、从尾到头打印单链表-栈
利用栈FILO的性质，先存储节点然后输出每个栈的节点值
<span style="font-family:Microsoft YaHei;font-size:14px;">// 从尾到头打印单链表（栈）
public void reList2(Node head) {
Stack<Node> s = new Stack<Node>();
while (head != null) {
s.push(head);
head = head.next;
}
while (!s.isEmpty()) {
System.out.println(s.pop().value);
}
}</span>
9、由小到大合并有序单链表-循环
<span style="font-family:Microsoft YaHei;font-size:14px;"> // 由小到大合并俩个有序的单链表(循环)
public Node mergeSort1(Node head1, Node head2) {
// 安全性检查
if (head1 == null)
return head2;
if (head2 == null)
return head1;
// 新建合并节点
Node target = null;
// 确定第一个元素的节点
if (head1.value > head2.value) {
target = head2;
head2 = head2.next;
} else {
target = head1;
head1 = head1.next;
}
target.next = null;
// 开始合并
Node mergeHead = target;
while (head1 != null && head2 != null) {
// 当两个链表都不为空
if (head1.value > head2.value) {
target.next = head2;
head2 = head2.next;
} else {
target.next = head1;
head1 = head1.next;
}
target = target.next;
target.next = null;
}
if (head1 == null)
target.next = head2;
else
target.next = head1;
return mergeHead;
}</span>
10、由小到大合并有序单链表-递归
<span style="font-family:Microsoft YaHei;font-size:14px;">// 由小到大合并俩个有序的单链表(递归)
public Node mergeSort2(Node head1, Node head2) {
if (head1 == null)
return head2;
if (head2 == null)
return head1;
if (head1.value > head2.value) {
head2.next = mergeSort2(head2.next, head1);
return head2;
} else {
head1.next = mergeSort2(head1.next, head2);
return head1;
}
}</span>