[数据结构与算法]Java数据结构——链表练习题

1. 获取单链表的节点个数

实现思路：

从头结点开始遍历，并使用计数器进行计数即可

代码实现：

//获取单链表的节点个数
public static int getLength(SingleNode head) {
	if (head.next == null) {
		//空链表
		return 0;
	}
	int length = 0;
	SingleNode temp = head.next;
	while (temp != null) {
		length++;
		temp = temp.next;
	}
	return length;
}

2.?查找单链表中的倒数第index个节点

实现思路：

进行两次遍历

第一次遍历得到链表的长度

第二次遍历首先让temp指向第一个节点，然后往后遍历 size - index 个节点即可

代码实现：

//查找单链表中的倒数第index个节点
public static SingleNode findLastIndexNode(SingleNode head, int index) {
	if (head.next == null) {
		//空链表
		return null;
	}
	//第一次遍历得到链表长度
	int size = getLength(head);
	//校验index
	if (index <= 0 || index > size) {
		return null;
	}
	//第二次遍历首先让temp指向第一个节点，然后往后遍历 size - index 个，即为倒数第index个节点
	SingleNode temp = head.next;
	for (int i = 0; i < size - index; i++) {
		temp = temp.next;
	}
	return temp;
}

3. 单链表的反转

实现思路：

若链表为空或只有一个节点，无需做任何处理

创建两个临时节点temp和next，分别指向当前遍历到的节点及其下一个节点

创建一个新的头结点用于保存反转后的链表

遍历原来的链表，每遍历一个节点，就将其取出放在新链表的最前面

最后将原链表的头结点的next指向新链表头结点的next即可

代码实现：

//单链表的反转
public static void reverseList(SingleNode head) {
	if (head.next == null || head.next.next == null) {
		//空链表或只有一个节点
		return;
	}
	SingleNode temp = head.next;
	SingleNode next = null;    //指向当前节点的下一个节点
	SingleNode reverseHead = new SingleNode(0);
	//遍历原来的链表，每遍历一个节点，就将其取出放在新链表reverseHead的最前面
	while (temp != null) {
		next = temp.next;
		temp.next = reverseHead.next;
		reverseHead.next = temp;
		temp = next;
	}
	head.next = reverseHead.next;
}

4. 从尾到头打印单链表

实现思路：

方法一：可利用上题中的单链表的反转实现，不再赘述

方法二：利用栈结构实现

将各个节点压入栈中，并依次出栈并打印即可

代码实现：

//从尾到头打印单链表
public static void reversePrint(SingleNode head) {
	if (head.next == null) {
		//空链表
		return;
	}
	//创建一个栈，将各个节点压入栈中
	Stack<SingleNode> stack = new Stack<>();
	SingleNode temp = head.next;
	while (temp != null) {
		stack.push(temp);
		temp = temp.next;
	}
	//打印栈中节点
	while (stack.size() > 0) {
		System.out.println(stack.pop());
	}
}

5. 合并两个有序单链表，合并后的链表仍然有序

实现思路：

创建两个临时变量temp1、temp2指向对传入的两个链表遍历的当前节点

创建两个临时变量next1、next2指向两个链表当前节点的下一个节点

创建需要返回的链表，并用临时变量temp指向其头结点

循环中，首先判断temp1和temp2是否为null，若为null则说明有一个链表已经没有节点了，只需要将另一个链表整个插入到返回链表的最后即可。

若temp1和temp2均不为空，则使用临时变量next1、next2分别保存它们的下一个元素

比较两个链表中当前节点的数据大小，将数据小的节点的next置空（与原链表断开），将其插入到返回链表的最后，并将返回链表的指针后移，将刚刚数据小的节点的链表的当前节点指针后移

若两者数据相同，则同时加入到返回链表中并都后移即可

代码实现：

//合并两个有序单链表，合并后的链表仍然有序
public static SingleLinkedList merge(SingleNode head1, SingleNode head2) {
	SingleLinkedList singleLinkedList = new SingleLinkedList();
	SingleNode temp = singleLinkedList.getHead();
	SingleNode temp1 = head1.next;
	SingleNode next1 = null;
	SingleNode temp2 = head2.next;
	SingleNode next2 = null;
	while (true) {
		if (temp1 == null) {
			temp.next = temp2;
			break;
		}
		if (temp2 == null) {
			temp.next = temp1;
			break;
		}
		next1 = temp1.next;
		next2 = temp2.next;
		if (temp1.data > temp2.data) {
			temp2.next = null;
			temp.next = temp2;
			temp = temp.next;
			temp2 = next2;
		} else if (temp1.data < temp2.data) {
			temp1.next = null;
			temp.next = temp1;
			temp = temp.next;
			temp1 = next1;
		} else {
			temp1.next = null;
			temp2.next = null;
			temp.next = temp1;
			temp = temp.next;
			temp.next = temp2;
			temp = temp.next;
			temp1 = next1;
			temp2 = next2;
		}
	}
	return singleLinkedList;
}