链表5个常见操作：单链表反转、链表中环的检测、两个有序单链表的合并、删除链表中的倒数第n个结点、求链表的中间结点_单链表反转 链表中环的检测 两个有序的链表合并 删除链表倒数第n个结点 求链表的

链表5个常见操作：

初学链表手写链表代码时很容易出现各种各样的错误，这还导致需要写代码时有了很大的心理障碍，但是在自己把这几个常见的链表操作写熟练后对链表中终于不再望而生畏了，记录一下。

• 单链表反转
• 链表中环的检测
• 两个有序链表合并
• 删除链表倒数第n个结点
• 求链表的中间结点

---

链表实现：

public class Node {
	int data;
	Node next;
	
	Node(int data){
		this.data = data;
	}
}
1
2
3
4
5
6
7
8

单链表反转：

单链表反转有迭代反转法、递归反转法、就地逆置反转法、头插法四种实现方法。

1. 迭代反转链表
   设置三个指针beg、mid、end，beg指针指向mid指针的前一个指针，end指针指向mid指针的后一个指针，初始状态mid指针指向头结点，然后遍历链表，依次改变mid指针的next指针，使其指向前一个结点，随后将三个指针后移直至mid指针遍历完链表。
   实现：

	//单链表反转：迭代法
	public static Node reverseByLoop(Node head) {
		if(head == null || head.next == null) {
			return head;
		}
		Node pre = null;
		Node next = null;
		while(head != null) {
			next = head.next;
			head.next = pre;
			pre = head;
			head = next;
		}
		return pre;
	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2. 递归反转链表
   递归到链表的尾结点，从尾结点开始依次向前遍历，遍历过程中依次改变各结点的指向，使其next指针指向前一个结点。
   实现：

//单链表反转：递归反转法
	public static Node reverseByRecursion(Node head) {
		if(head == null || head.next ==null) {
			return head;
		}
		
		Node newNode = reverseByRecursion(head.next);
		head.next.next = head;
		head.next = null;
		return newNode;
	}
1
2
3
4
5
6
7
8
9
10
11

3. 头插法反转链表：
   在原有链表的基础上，依次将链表的结点摘下，然后采用从头部插入的方式生成一个新链表。
   实现：

//单链表反转：头插法
	public static Node reverseByAdd(Node head) {
		Node newHead = null;
		Node tmp = null;
		if(head == null ||head.next == null) {
			return head;
		}
		while(head != null) {
			tmp = head;
			head = head.next;
			tmp.next = newHead;
			newHead = tmp;
		}
		return newHead;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

4. 就地转置法反转链表：
   就地转置法和头插法的实现思想类似，区别在于，头插法通过一个新链表实现，而就地转置法直接对原链表做修改，从而实现原链表反转。
   实现：

//单链表反转：就地逆转法
	public static Node reverseByAddlocal(Node head) {
		
		Node beg = null;
		Node end = null;
		if(head == null || head.next == null) {
			return head;
		}
		beg = head;
		end = head.next;
		while(end != null) {
			beg.next = end.next;//beg 新链表的尾指针，beg.next指向
			end.next = head;//end指向将反转的第一个节点
			head = end;//head指向反转链表的最后一个节点，即反转后的头指针
			end = beg.next;
		}
		return head;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

链表中环的检测：

链表中环的检测可通过快慢指针法和足迹法实现

1. 快慢指针法：
   设置快慢指针，快指针一次前进两个结点，慢指针一次前进一个结点 ，如果链表中存在环，则快指针一定会与慢指针相遇；如果不存在环，则快指针比慢指针提前到达链表尾部。
   实现：

//链表中环的检测：快慢指针法
	public static boolean hasLoopV1(Node head) {
		if(head == null) {
			return false;
		}
		
		Node slow = head;
		Node fast = head.next;
		
		while(fast != null && fast.next != null) {
			slow = slow.next;
			fast = fast.next.next;
			
			if(fast == null) {
				return false;
			}else if(fast == slow) {
				return true;
			}
		}
		return false;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3. 足迹法：
   顺序遍历链表中的所有结点，并将其记录下来，若某个结点的信息出现两次，则存在环。
   实现：

	private static HashMap<Node,Integer> nodeMap = new HashMap<>();
	//链表中环的检测：足迹法
	public static boolean hasLoopV2(Node node,int index) {
		if(node == null || node.next == null) {
			return false;
		}
		if(nodeMap.containsKey(node) && nodeMap.get(node)== index) {//？？？如果链表中含有相同元素但不存在环 这个写法错误 必须同时判断node和index 解决：nodeMap.get(node)== index
			return true;
		}else {
			nodeMap.put(node, index);
			return hasLoopV2(node.next,++index);
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13

两个有序单链表的合并

1. 两个链表a、b是否都为空，是则返回null
2. 一个链表为空另一个链表不为空，返回不为空的那个链表
3. 两个链表都不为空

• 递归法

  假如：list1为： 1 --> 3 --> 5 – null ; list2为：2 --> 4 --> 6 --> 8 – > null; 我们指定head用来存放data小的那个对象，刚开始时list与list实际是指向了两个链表的表头，即list1.data = 1 , list2.data = 2 ,此时我们发现1 <= 2 ,我们将head指向list1 ，那么新问题就是：head的next指向哪？递归算法的魅力就在这，我们不用考虑别的，反正一定是在两个链表剩下的元素中，那么我们将list1.next和list2作为递归方法的参数，继续调用递归方法即可。
  我们发现当list1指向null时，list并没有指向null，就是说本例中list2中还有元素没有被合并，那么在实际中可能是list1也可能是list2会有元素没有合并，但其中一个已经已经是null了，此时只需判断哪个非null，将其合并在后面即可

实现：

//合并两个有序链表：递归法
	public static Node mergeTwoList(Node head1,Node head2) {
		if(head1 == null) {
			return head2;
		}else if(head2 == null) {
			return head1;
		}
		Node head = null;
		if(head1.data < head2.data) {
			head = head1;
			head.next = mergeTwoList(head1.next,head2);
		}else {
			head = head2;
			head.next = mergeTwoList(head1,head2.next);
		}
		return head;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 非递归法

  传入的两个链表是node1和node2 ， 开头和递归算法一样，也是那三种情况，前两种情况处理也一样，关键在第三种情况，此时我们这么考虑，node1是一个在node1链表上的指针，node2是node2链表上的一个指针，我们有一个新的指针head,在两个指针所指都不是null时，我们让head指向data更小的那个，同样：
  假如list1为： 1 --> 3 --> 5 – null ; list2为：2 --> 4 --> 6 --> 8 – > null;
  刚开始1 < 2 , 让head = list1 , 然后list1 = list.next, 使用另一个指针Node point = head 来记注这个合并后链表的移动，
  现在再看那么list1.data = 3 , list2.data = 2 , 2 < 3 ，那么head.next = list2 , list2 = list2.next ， 在让point指针也向着后移动，即point = point.next ,
  …
  其实就是使用四个指针，一个记录node1上的当前位置(list1)，一个记录node2上的当前位置(list2)，一个记录合并链表的表头(head)，另外一个不断的指向当前位置下data更小的那一个(point)

实现：

//合并两个有序链表：非递归法
	public static Node mergeTwoList2(Node head1,Node head2) {
		//头指针指向合并后链表的表头，初始指向较小data的节点
		Node head = head1.data<head2.data ? head1 : head2;
		
		//list1存储的是第一次比较后data较小链表的当前位置，此时需要指向下一个节点；list2存储另一链表的当前节点
		Node list1 = head==head1 ? head1.next : head2.next;
		Node list2 = head==head1 ? head2 : head1;
		//point指向合并链表的下一个节点
		Node point = head;
		//循环遍历，根据data的比较结果判断point的下一节点
		while(list1 != null && list2 != null) {
			if(list1.data < list2.data) {
				point.next = list1;
				list1 = list1.next;
			}else {
				point.next = list2;
				list2 = list2.next;
			}
			point = point.next;
		}
		point.next = list1==null ? list2 : list1;
	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---

删除链表中倒数第n个结点：

设置快慢指针，快指针首先向前走n步，则快指针和慢指针之间相隔n步，当快指针指向最后一个结点时，慢指针指向倒数第n+1个结点，则可删除倒数第n个结点。
实现：

//删除链表中倒数第n个数
	public static Node removeNodeByEndNum(Node head,int n) {		
		Node fast = head;
		Node slow = head;
		//快指针遍历
		while(n-- > 0) {
			if(fast == null) {
				return head;
			}
			fast = fast.next;
		}
		while(fast != null && fast.next !=null) {
			fast = fast.next;
			slow = slow.next;
		}
		if(slow == head) {
			head = head.next;
		}else {
			slow.next = slow.next.next;
		}
		return head;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

求链表的中间结点：

设置快慢指针，快指针一次走两步，慢指针一次走一步，快指针的速度是慢指针的两倍，所以当快指针遍历完链表时，慢指针遍历至中间结点。
实现：

//求链表的中间节点，链表元素为偶数个数时返回第n/2 + 1个元素
	public static Node findMiddleNode(Node head) {
		if(head == null || head.next == null) {
			return null;
		}
		Node fast = head.next;
		Node slow = head;
		while(fast != null && fast.next != null) {
			fast = fast.next.next;
			slow = slow.next;
		}
		return fast==null ? slow :slow.next;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13

LeetCode相关练习题：206, 141, 21, 19, 876