我的简书：https://www.jianshu.com/u/c91e642c4d90
我的CSDN：http://blog.csdn.net/wo_ha
我的GitHub：https://github.com/chuanqiLjp
我的个人博客：https://chuanqiljp.github.io/
版权声明：商业转载请联系我获得授权，非商业转载请在醒目位置注明出处。
1. 单链表反转;
public Node inverseLinkList(Node head) {//将头结点为head的链表进行反转,返回反转后的头结点的链表
Node pre_node = null;
Node cur_node = head;
Node nex_node = null;
if (head == null || head.next == null) return head;
while (cur_node != null) {
nex_node = cur_node.next;
cur_node.next = pre_node;
pre_node = cur_node;
cur_node = nex_node;
}
return pre_node;
}
2. 链表中环的检测;
/**
* 检测链表中的环形: 快慢指针法
* 首先设置两个指针，分别命名为fast和slow，fast指针每次向后移2步，slow指针每次向后移1步。如果，fast指针最后走到尾结点，则没有环。如果，fast指针和slow指针相遇，则证明有环。
* 环的起始结点的查询: 当fast与slow相遇之后，fast指针从头结点开始走，每次走1步,当fast再次与slow相遇以后，相遇处的结点为环的入口结点
*
* @param head 待检测的链表
* @return 环结点的入口, null表示无环结点
*/
public Node checkLinkRing_v1(final Node head) {
Node ringIn_node = null;
if (head == null || head.next == null || head.next.next == null) {
return null;
}
Node fast_node = head;
Node slow_node = head;
int count = 0;//相遇的次数
while (fast_node != null && slow_node != null) {
if (fast_node.next == null) {//走到了尾结点,不可能有环
break;
}
if (ringIn_node == null) {
fast_node = fast_node.next.next;
} else {
if (count == 1) {
fast_node = head;
}
fast_node = fast_node.next;
}
slow_node = slow_node.next;
if (fast_node == slow_node) {
count++;
ringIn_node = fast_node;
if (count == 2) {
break;
}
}
}
return ringIn_node;
}
/**
* 足迹法: 顺序遍历链表中所有的节点，并将所有遍历过的节点信息保存下来。如果某个节点的信息出现了两次，则存在环。
* @param head
* @return
*/
public boolean checkLinkRing_v2(final Node head) {
boolean result = false;
HashMap<Node, Node> map = new HashMap<>();
Node p = head;
while (p != null) {
if (map.containsKey(p)) {
return true;
}
map.put(p, p);
p = p.next;
}
return result;
}
3. 两个有序的链表合并;
/**
* 通过比较,每次只拷贝小的数据到合并后的链表中,原有链表结构不会被破坏
*
* @param h1
* @param h2
* @return 合并后的链表的头
*/
public static Node mergeOrderlyLink_v1(final Node h1, final Node h2) {
Node tem = h1 != null ? h1 : h2;
if (h1 == null || h2 == null) {
return tem;
}
Node merge = null;
Node p1 = h1, p2 = h2;
Node pm = new Node(-1, null);//自定义一个头结点
int i = 0;
while (p1 != null && p2 != null) {//比较大小,将小的拷贝到合并后的链表中
if (p1.data <= p2.data) {
pm.next = new Node(p1.data, null);
p1 = p1.next;
} else {
pm.next = new Node(p2.data, null);
p2 = p2.next;
}
if (i == 0) {
merge = pm;
}
pm = pm.next;
i++;
}
tem = p1 == null ? p2 : p1;
while (tem != null) {//拷贝剩余的数据追加到合并后的链表中
pm.next = new Node(tem.data, null);
pm = pm.next;
tem = tem.next;
}
merge = merge.next;//去除自定义的头结点
return merge;
}
/**
* 递归合并有序链表,原有链表结构会被破坏,数据较大时容易发生堆栈溢出异常,
* 说明参考链接:https://blog.csdn.net/fengpojian/article/details/81384130实现
*
* @param h1
* @param h2
* @return
*/
public static Node mergeOrderlyLink_v2(final Node h1, final Node h2) {
Node tem = h1 != null ? h1 : h2;
if (h1 == null || h2 == null) {
return tem;
}
Node merge = null;
if (h1.data <= h2.data) {
merge = h1;
merge.next = mergeOrderlyLink_v2(h1.next, h2);
} else {
merge = h2;
merge.next = mergeOrderlyLink_v2(h1, h2.next);
}
return merge;
}
4. 删除链表倒数第 n 个结点(n 保证有效);
/**
* 一次遍历法: 使用快慢指针。快指针比慢指针提前n个单元。当快指针到达单链表尾部时，慢指针指向待删除节点的前节点。
*
* @param head
* @param beforIndex 保证有效,从 1 开始
* @return
*/
public static Node deleteIndexFormEnd_v2(final Node head, int beforIndex) {
Node fast = head;
Node slow = head;
for (int i = 0; i < beforIndex; i++) {
fast = fast.next;
}
if (fast == null) {
return head.next;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return head;
}
/**
* 常规做法: 遍历第一次求出链表的长度,遍历第二次删除
*
* @param head
* @param beforIndex 保证有效,从 1 开始
* @return
*/
public static Node deleteIndexFormEnd_v1(final Node head, int beforIndex) {
int size = 0;
Node p = head;
while (p != null) {
p = p.next;
size++;
}
if (beforIndex == size) {//删除头结点
return head.next;
}
int count = 0;
int k = size - beforIndex;
p = head;//复位
Node pre = p; //记录要寻找到的删除的结点的上结点
while (p != null) {
if (count == k) {//找到要删除的结点
pre.next = p.next;
break;
}
pre = p;
p = p.next;
count++;
}
return head;
}
5. 求链表的中间结点;
/**
* 寻找链表的中间结点: 设置两个指针，一个快指针，每次走两步，一个慢指针，每次走一步。
* 常规做法: 先遍历整个链表求长度在遍历一次找到中间结点,代码省略
*
* @param head
* @return
*/
public static Node findCenterNode(Node head) {
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
