JAVA链表

Posted on | In | Visitors:

一些链表题目的 java 解答

1. 求单链表中的结点数

1
2
3
4
5
6
7
8
public static int getListLength(Node head) {
	int len = 0;
	while(head != null) {
		len++;
		head = head.next;
	}
	return len;
}

2. 将单链表反转

1、循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
 * 因为在对链表进行反转的时候，需要更新每一个node的“next”值，
 * 但是，在更新 next 的值前，需要保存 next 的值，否则无法继续。
 * 所以，我们需要两个指针,分别指向前一个节点和后一个节点，
 * 每次做完当前节点“next”值更新后，把两个节点往下移，直到到达最后节点。
 */
public static Node reverseList(Node head) {
	if(head == null || head.next == null) {
		return head;
	}
	//指向前一个结点
	Node pre = null;
	//指向后一个结点
	Node nex = null;
	while(head != null) {
		//保存后一个结点
		nex= head.next;
		//反转后的头结点就是原始链表的尾结点
		if (nex = null) {
			pre = head;
		}
		//更新当前结点的 next 值
		head.next = pre;
		//将两个结点向下移
		pre = head;
		head = nex;
	}
	return pre;
}

2、递归

1
2
3
4
5
6
7
8
9
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;		
}

3. 查找链表倒数第 k 个结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/*
 * 设置两个结点，使其距离为 k ，共同移动直至第二个结点为null
 */
public static Node reGetKthNode(Node head, int k) {
	if (head == null) {
		return head;
	}
	int len = getListLength(head);
	if (k > len) {
		return null;
	}
	Node target = head;
	Node nex = head;
	// 让 nex 结点往后移动 k 个位置
	for (int i = 0; i < k; i++) {
		nex = nex.next;
	}
	//让 target 和 nex 结点整体向后移动，直到 nex　结点为null
	while (nex != null) {
		target = target.next;
		nex = nex.next;
	}
	return target;
}

4. 查找链表中间结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static Node getMiddleNode(Node head) {
	if (head == null || head.next == null) {
		return head;
	}
	//设置两个结点
	Node target = head;
	Node temp = head;
	//两个结点同时向下移动
	while (temp != null && temp.next != null) {
		//target 结点一次移动一步
		target = target.next;
		//temp 结点一次移动两步
		temp = temp.next.next;
	}
	//当 temp 移动到结点 null，target 即为中间结点位置
	return target;
}

5. 从尾到头打印链表

1、递归

1
2
3
4
5
6
7
8
9
public static void reversePrintListRec(Node head) {
	if(head == null) {
		return;
	}
	else {
		reversePrintListRec(head.next);
		System.out.println(head.value);
	}
}

2、栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void reversePrintListStack(Node head) {
	//新建一个栈
	Stack<Node> stack = new Stack<Node>();
	//将链表的所有结点压栈
	while (head != null) {
		stack.push(head);
		head = head.next;
	}
	//出栈、打印
	while (!stack.isEmpty()) {
		result = stack.pop().value
		System.out.println(result);
	}
}

6. 合并两个有序的单链表

1、循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public static Node mergeSortedList(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) {  //说明 head1 遍历完了
		target.next = head2;
	}
	if (head2 == null) {
		target.next = head1;
	}
	return mergeHead;
}

2、递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
publc static Node mergeSortedListRec (Node head1, Node head2) {
	if (head1 == null) {
		return head2;
	}
	if (head2 == null) {
		return head1;
	}
	if (head1.value > head2.value) {
		head2.next = mergeSortedListRec(head2.next, head1);
		return head2;
	}
	else {
		head1.next = mergeSortedListRec(head1.next, head2);
		return head1;
	}
}

7. 对单链表进归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static Node listSort (Node head) {
	Node nex = null;
	if (head == null || head.next == null) {
		return head;
	}
	else if (head.next.next == null) {
		nex = head.next;
		head.next = null;
	}
	//把链表从中间分开来
	else {
		//调用 getMiddleNode(),得到链表的中间结点
		Node mid = getMiddleNode(head);  
		nex = mid.next;
		mid.next = null;
	}
	//合并两个有序的单链表，不要用递归的合并算法，可能栈溢出
	return mergeSortedList(listSort(head), listSort(nex)); 
}

8. 对单链表插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public static Node insertionSortList (Node head) {
	if (head == null || head.next == null) {
	return head;
	} 
	Node pnex = head.next; //未排序的游动指针
	Node pnex_nex = null;
	head.next = null;
	while (pnex != null) {
		pnex_nex = pnex.next; //pnex：临时结点指针
		Node temp = head;
		Node temp_pre = null;
		while (temp != null) {
			if (temp.value > pnex.value) {
				break;
			}
			temp_pre = temp;
			temp = temp.next;
		}
		if (temp_pre == null) {
			head = pnex;
			pnex.next = temp;
		}
		else {
			temp_pre.next = pnex;
			pnex.next = temp;
		}
		pnex = pnex_nex;
	}
	return head;
}

9.判断链表是否有环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//用快慢指针
public static boolean hasCycle(Node head) {
	boolean flag = false;
	Node slow = head;
	Node fast = head;
	while (slow != null && fast != null) {
		slow = slow.next;
		fast = fast.next.next;
		if (slow == fast) {
			flag = true;
			break;
		}
	}
	return flag;
}

10.求环的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
 * 继续使用快慢指针法。
 * 快慢指针相遇时一定是在环中，
 * 从这个结点出发，一边继续向前移动一边计数，
 * 再次回到这个结点时，就可以得到环中的结点数了
 */
public static int getCycleLength(Node head) {
	int cycleLength = 0;
	if (head == null) {
		return 0;
	}
	Node slow = head.next;
	if (slow == null) {
		return 0;
	}
	Node meet = null;
	Node fast = slow.next;
	while (fast != null && slow != null) {
		if (fast == slow) {
			meet = fast;
		}
		slow = slow.next;
		fast = fast.next;
		if (fast != null) {
			fast = fast.next;
		}
	}
	if (meet == null) {
		return 0;
	}
	Node temp = meet;
	while (temp.next != meet) {
		temp = temp.next;
		++cycleLength;
	}
	return cycleLength;
}

11.求环的入口结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 用《剑指offer中》第56题的思路
 * 设置两个指针 p1 和 p2，开始时都指向头结点，
 * 然后获得环的长度，让 p1 先移动环长的步数，
 * 让 p1 和 p2 以相同速度在链表上移动，直到相遇，相遇结点即为环的入口结点
 */
public static Node getFirstNodeInCycle(Node head) {
	//获得环中结点个数
	int nodesInLoop = getCycleLength(head);
	//p1先移动环长的步数
	Node p1 = head;
	for (int i = 0; i < nodesInLoop; i++) {
		p1 = p1.next;
	}
	//让 p1 和 p2 以相同速度移动，直到相遇
	Node p2 = head;
	while (p1 != p2) {
		p1 = p1.next;
		p2 = p2.next;
	}
	return p1;
}

12.两个相交链表的第一个结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
 * 如果单纯的判断是否相交，只需要看最后一个指针是否相等即可
 */
public static Node isIntersect(Node head1, Node head2) {
	Node target = null;
	if (head1 == null || head2 == null) {
		return target;
	}
	int len1 = getListLength(head1);
	int len2 = getListLength(head2);
    int lengthDif = 0;  //两个单链表长度的差值
	Node longHead;
	Node shortHead;
	//找出较长的那个链表
	if(len1 > len2) {
		longHead = head1;
		shortHead = head2;
	} else {
		longHead = head2;
		shortHead = head1;
	}
	//将较长的那个链表的指针向前走 lengthDif 步
	for (int i = 0; i < lengthDif; i++) {
		longHead = longHead.next;
	}
	//将两个链表的指针同时向前移动
	while (longHead != null && shortHead != null) {
       	if (longHead == shortHead) {
	        target = longHead;
		    break;
	    }
	    else {
		    longHead = longHead.next;
		    shortHead = shortHead.next;
	    }
    }
	return target;
}