链表相关算法

一、简介

链表是一种线性表，它由一系列节点组成，每个节点包括存储数据元素的数据域和存储下一个节点地址的指针域。 链表有多种类型，包括单向链表、双向链表、循环链表等。单向链表中的每个节点只有一个指向下一节点的指针；双向链表中的每个节点有两个指针，分别指向前一节点和后一节点；循环链表则是首尾相连的链表。

• 优点

  • 插入和删除操作效率高：链表在插入和删除节点时，只需要修改相关节点的指针即可，而不需要像数组那样移动大量元素，可以达到O(1)的复杂度。
  • 内存管理灵活：链表克服了数组需要预先知道数据大小的缺点，可以充分利用内存空间，实现内存的动态管理。

• 缺点

  • 查询效率低：链表不具备随机访问的特性，每次查询都需要从头节点开始遍历，时间复杂度为O(n)。
  • 空间开销大：链表由于增加了节点的指针域，相较于数组等结构，空间开销较大。

二、算法题

• 链表类

public class LinkNode {

	int data;
	LinkNode next;
	
	public LinkNode(int data) {
		this.data = data;
	}
	
	public void print(){
		LinkNode cur = this;
		while(cur != null){
			System.out.print(cur.data + " ");
			cur = cur.next;
		}
	}
	
	public static LinkNode createNode(int[] arr){
		LinkNode dummy = new LinkNode(0);
		LinkNode cur = dummy;
		for(int val : arr){
			cur.next = new LinkNode(val);
			cur = cur.next;
		}
		return dummy.next;
	}
}

1、添加/删除节点

使用哨兵节点简化操作：

• 添加节点

public LinkNode append(LinkNode node, int val){
	LinkNode dummy = new LinkNode(0);
	dummy.next = node;
	
	LinkNode cur = dummy;
	while(cur.next != null){
		cur = cur.next;
	}
	cur.next = new LinkNode(val);
	return dummy.next;
}

• 删除节点

public LinkNode delete(LinkNode node, int val){
	LinkNode dummy = new LinkNode(0);
	dummy.next = node;
	
	LinkNode cur = dummy;
	while(cur.next != null){
		if(cur.next.data == val){
			cur.next = cur.next.next;
			break;
		}
		cur = cur.next;
	}
	return dummy.next;
}

2、两数相加

将两个使用链表表示的数相加（例如：3->1->5表示513）

private static LinkNode addLinkNode(LinkNode node1, LinkNode node2) {
	LinkNode dummy = new LinkNode(0);
	LinkNode cur = dummy;
	LinkNode cur1 = node1;
	LinkNode cur2 = node2;
	int carry = 0;
	while(cur1 != null && cur2 != null){
		int sum = cur1.data + cur2.data + carry;
		carry = sum / 10;
		LinkNode temp = new LinkNode(sum % 10);
		cur.next = temp;
		cur = temp;
		cur1 = cur1.next;
		cur2 = cur2.next;
	}
	cur1 = cur1 != null ? cur1 : cur2;
	while(cur1 != null){
		int sum = cur1.data + carry;
		carry = sum / 10;
		LinkNode temp = new LinkNode(sum % 10);
		cur.next = temp;
		cur = temp;
		cur1 = cur1.next;
	}
	return dummy.next;
}

public static void main(String[] args) {
	LinkNode node1 = LinkNode.createNode(new int[] {3, 4, 5, 6, 7, 8, 2});
	LinkNode node2 = LinkNode.createNode(new int[] {9, 8, 7, 6, 5});
	LinkNode ret = addLinkNode(node1, node2);
	ret.print();
}

输出：

2 3 3 3 3 9 2 

3、删除重复元素

• 删除链表中的重复元素

public static void main(String[] args) {
	LinkNode node = LinkNode.createNode(new int[] {1, 2, 3, 1, 3, 5, 5, 7, 8, 7});
	LinkNode inner = node;
	while(inner != null){
		LinkNode prev = inner; 
		LinkNode outer = inner.next;
		while(outer != null){
			if(inner.data == outer.data){
				prev.next = outer.next;
			}
			prev = outer;
			outer = outer.next;
		}
		inner = inner.next;
	}
	node.print();
}

输出:

1 2 3 5 7 8 

• 删除已排序链表中的所有重复元素，使每个元素只出现一次

public static void main(String[] args) {
	//1->1->2->3->3
	LinkNode node = LinkNode.createNode(new int[]{1, 1, 2, 3, 3});
	LinkNode cur = node;
	while(cur != null && cur.next != null){
		if(cur.data == cur.next.data){
			cur.next = cur.next.next;
		}else{
			cur = cur.next;
		}
	}
	node.print();
}

输出：

1 2 3

4、倒数第k个元素

找出链表中倒数第k个元素。

private static LinkNode findLastK(LinkNode node, int k) {
	LinkNode fast = node;
	for(int i = 0; i < k; i++){
		fast = fast.next;
	}
	LinkNode slow = node;
	while(fast != null){
		fast = fast.next;
		slow = slow.next;
	}
	return slow;
}

public static void main(String[] args) {
	//1->2->3->4->5->6->7
	LinkNode node = LinkNode.createNode(new int[]{1, 2, 3, 4, 5, 6, 7});
	LinkNode ret = findLastK(node, 3);
	System.out.println(ret.data);
}

5、链表转数字

计算链表表示的数的大小，例如：链表1->0->0表示数字4。

public static void main(String[] args) {
	LinkNode node = LinkNode.createNode(new int[]{1, 0, 1});
	int sum = 0;
	LinkNode cur = node;
	while(cur != null){
		sum = sum * 2 + cur.data;
		cur = cur.next;
	}	
	System.out.println(sum);
}

输出：

5

6、链表相交结点

计算两个链表相交的结点。

public LinkNode getIntersect(LinkNode node1, LinkNode node2){
	int len1 = 0;
	LinkNode cur1 = node1;
	while(cur1 != null){
		len1++;
		cur1 = cur1.next;
	}
	
	int len2 = 0;
	LinkNode cur2 = node2;
	while(cur2 != null){
		len2++;
		cur2 = cur2.next;
	}
	
	//长度差
	int detal = Math.abs(len1 - len2);
	
	LinkNode longer = null;
	LinkNode shorter = null;
	if(len1 > len2){
		longer = node1;
		shorter = node2;
	}else{
		longer = node2;
		shorter = node1;
	}
	
	//长链表先遍历detal步
	LinkNode lcur = longer;
	for(int i = 0; i < detal; i++){
		lcur = lcur.next;
	}
	
	LinkNode scur = shorter; 
	while(lcur != scur){
		lcur = lcur.next;
		scur = scur.next;
	}
	
	return lcur;
}

7、相邻结点间插入新结点

在链表的相邻两个结点间插入一个新的结点, 新结点的值为这两个相邻结点的最大公约数。

private static int getGreatestCommonDivisor(int a, int b) {
	while(b != 0) {
		int tmp = a % b;
		a = b;
		b = tmp;
	}
	return a;
}

public static void main(String[] args) {
	LinkNode node = LinkNode.createNode(new int[] {18, 6, 10, 3, 7, 35});
	LinkNode cur = node;
	while(cur != null && cur.next != null){
		int gcd = getGreatestCommonDivisor(cur.data, cur.next.data);
		LinkNode temp = new LinkNode(gcd);
		LinkNode next = cur.next;
		cur.next = temp;
		temp.next = next;
		cur = next.next;
	}
	node.print();
}

8、合并两个链表

两个升序链表合并为一个新的升序链表。

public static void main(String[] args) {
	LinkNode node1 = LinkNode.createNode(new int[]{1, 2, 4});
	LinkNode node2 = LinkNode.createNode(new int[]{1, 3, 4});
	
	LinkNode dummy = new LinkNode(0);
	LinkNode cur = dummy;
	LinkNode cur1 = node1;
	LinkNode cur2 = node2;
	
	while(cur1 != null && cur2 != null){
		if(cur1.data < cur2.data){
			cur.next = cur1;
			cur1 = cur1.next;
		}else{
			cur.next = cur2;
			cur2 = cur2.next;
		}
		cur = cur.next;
	}
	
	cur.next = cur1 != null ? cur1 : cur2;
	dummy.next.print();
}

9、链表中间结点

public static void main(String[] args) {
	LinkNode node = LinkNode.createNode(new int[]{1, 2, 3, 4, 5});
	LinkNode fast = node;
	LinkNode slow = node;
	while(fast != null && fast.next != null){
		fast = fast.next.next;
		slow = slow.next;
	}
	System.out.println(slow.data);
}

输出：

3

如果链表为：1->2->3->4->5->6，则输出4。

10、删除倒数第k个元素

public static void main(String[] args) {
	LinkNode node = LinkNode.createNode(new int[]{1, 2, 3, 4, 5, 6});
	int k = 3;
	LinkNode fast = node;
	for(int i = 0; i < k + 1; i++){
		fast = fast.next;
	}
	LinkNode slow = node;
	while(fast != null){
		fast = fast.next;
		slow = slow.next;
	}
	slow.next = slow.next.next;
	node.print();
}

输出：

1 2 3 5 6 

11、删除元素

删除链表中所有值为val的结点。

public static void main(String[] args) {
	LinkNode node = LinkNode.createNode(new int[]{6, 1, 2, 6, 3, 4, 5, 6});
	int val = 6;
	
	LinkNode dummy = new LinkNode(0);
	dummy.next = node;
	
	LinkNode prev = dummy;
	LinkNode cur = node;
	while(cur != null){
		if(cur.data == val){
			prev.next = cur.next;
		}else{
			prev = cur;
		}
		cur = cur.next;
	}
	dummy.next.print();
}

输出：

1 2 3 4 5 

12、反转链表

private static LinkNode reverse(LinkNode node){
	LinkNode prev = null;
	LinkNode cur = node;
	while(cur != null){
		LinkNode next = cur.next;
		cur.next = prev;
		prev = cur;
		cur = next;
	}
	return prev;
}

public static void main(String[] args) {
	LinkNode node = LinkNode.createNode(new int[]{1, 2, 3, 4, 5});
	LinkNode ret = reverse(node);
	ret.print();
}

输出：

5 4 3 2 1 

13、判断是否回文链表

例如：链表1->2->3->3->2->1和1->2->3->2->1均为回文链表。

public static void main(String[] args) {
	LinkNode node = LinkNode.createNode(new int[]{1, 2, 3, 2, 1});
	System.out.println(isPalindrome(node));//true
}

private static boolean isPalindrome(LinkNode node){
	if(node == null || node.next == null){
		return true;
	}
	LinkNode slow = node;
	LinkNode fast = node.next;
	while(fast.next != null && fast.next.next != null){
		fast = fast.next.next;
		slow = slow.next;
	}
	
	LinkNode anotherHead = slow.next;
	if(fast.next != null){
		anotherHead = slow.next.next;
	}
	slow.next = null;
	
	return equals(node, reverse(anotherHead));
}

private static boolean equals(LinkNode node, LinkNode anotherHead) {
	LinkNode cur1 = node;
	LinkNode cur2 = anotherHead;
	while(cur1 != null && cur2 != null){
		if(cur1.data != cur2.data){
			return false;
		}
		cur1 = cur1.next;
		cur2 = cur2.next;
	}
	return cur1 == null && cur2 == null;
}

private static LinkNode reverse(LinkNode node){
	LinkNode cur = node;
	LinkNode prev = null;
	while(cur != null){
		LinkNode next = cur.next;
		cur.next = prev;
		prev = cur;
		cur = next;
	}
	return prev;
}

14、判断是否有环

public static void main(String[] args) {
	//0->1->2->3->1
	LinkNode head = new LinkNode(0);
	LinkNode one = new LinkNode(1);
	head.next = one;
	LinkNode two = new LinkNode(2);
	one.next = two;
	LinkNode three = new LinkNode(3);
	two.next = three;
	three.next = one;
	
	System.out.println(isLoop(head));
}

private static boolean isLoop(LinkNode node){
	if(node == null || node.next == null){
		return false;
	}
	LinkNode slow = node.next;
	LinkNode fast = node.next;
	while(fast != null && fast.next != null){
		slow = slow.next;
		fast = fast.next.next;
		if(slow == fast){
			return true;
		}
	}
	return false;
}

15、链表重排列

输入：1->2->3->4->5->6

输出：1->6->2->5->3->4

public static void main(String[] args) {
	LinkNode node = LinkNode.createNode(new int[]{1, 2, 3, 4, 5, 6});
	LinkNode ret = reorder(node);
	ret.print();
}

private static LinkNode reorder(LinkNode head) {
	LinkNode dummy = new LinkNode(0);
	dummy.next = head;
	
	LinkNode fast = dummy;
	LinkNode slow = dummy;
	
	while(fast != null && fast.next != null) {
		fast = fast.next.next;
		slow = slow.next;
	}
	
	LinkNode anotherHead = slow.next;
	slow.next = null;
	
	return link(head, reverse(anotherHead));
}

private static LinkNode link(LinkNode head, LinkNode another) {
	LinkNode dummy = new LinkNode(0);
	LinkNode cur = dummy;
	
	LinkNode node1 = head;
	LinkNode node2 = another;
	
	while(node1 != null && node2 != null) {
		LinkNode temp = node1.next;
		cur.next = node1;
		node1.next = node2;
		
		cur = node2;
		node1 = temp;
		node2 = node2.next;
	}
	
	if(node1 != null) {
		cur.next = node1;
	}
	
	return dummy.next;
}

private static LinkNode reverse(LinkNode node){
	LinkNode prev = null;
	LinkNode cur = node;
	while(cur != null){
		LinkNode next = cur.next;
		cur.next = prev;
		prev = cur;
		cur = next;
	}
	return prev;
}