JAVA链表_2

一些链表题目的 java 解答(2)

13.删除链表中重复的结点

题目描述：

在一个已排序的链表中，如何删除重复的结点？
重复的结点不保留，返回链表头指针。
例如，链表 ：1->2->3->3->4->4->5 ，处理后为： 1->2->5

解答：

在一个排序的链表中，删除链表中重复的结点。循环
/*
 * 定义四个结点，前结点 pre，当前结点 temp，下一结点 nex，删除结点 deleteNode;
 * 在遇到删除结点时要保证 pre 连上 nex，防止断裂
 */
public static void deleteDuplication(Node head) {
	if (head == null) {
		return null;
	}
	if (head != null && head.next == null) {
		return head;
	}
	Node pre = null;  //前结点
	Node temp = head; //当前结点

	while (Node != null) {
		Node nex = temp.next;
		boolean needDelete = false;
		if (nex != null && nex.value == temp.value) {
			needDelete = true;
		}
		if (!needDelete) { //不重复，向前移动
			pre = temp;
			temp = temp.next;
		}
		else {  //重复，删除
			int value = temp.value;
			Node toBeDel = temp;
			while (toBeDel != null && toBeDel.value == value) {
				nex = toBeDel.next;
				toBeDel = nex;
			}
			if (pre == null) { //头结点删除时
				head = nex;
			}
			else {
				pre.next = nex;	
			}
			temp = nex;
		}
		return head;
	}	
}

14.复杂链表的复制

问题描述：

实现复杂链表的复制。在复杂链表中，每个结点除了有一个 next 指针指向下一个结点外，还有一个 Sibling 指向链表中的任意结点或者 null。

思路：

1. 根据原始链表的每个结点 N，创建对应的 N’。把 N’ 链接在 N 后面；
2. 设置复制出来的结点的 Sibling；
3. 将第二步的链表拆分成原始链表和复制出来的链表。

代码：

public class CloneComplexLinkedList {
	//复杂链表的构造器
	public class ListNode {
		int value;
		ListNode next;
		ListNode sibling;

		ListNode(int value) {
			this.value = value;
		}
	}
	//三步结合
	public static Node Clone (ListNode head) {
		copyNodes(head);
		connectSiblingNodes(head);
		return splitNodes(head);
	}

	//第一步，复制链表
	public static void copyNodes(ListNode head) {
		ListNode temp = head;
		while (head != null) {
			ListNode cloneNode = new ListNode(0);  // N'
			cloneNode.next = temp.next;
			cloneNode.value = temp.value;
			cloneNode.sibling = null;

			temp.next = cloneNode;
			//指针后移
			temp = cloneNode.next;
		}
	}

	//第二步，设置复制出来的结点、
	public static void connectSiblingNodes(ListNode head) {
		ListNode pNode = head;  // N
		while (head != null) {
			ListNode pCloned = pNode.next;  // N'
			if (pNode.sibling != null) {
				pCloned.sibling = pNode.sibling.next;
			}
			//指针后移
			pNode = pCloned.next;
		}
	}

	//第三步，将第二步得到的链表拆分
	public static ListNode splitNodes(ListNode head) {
		ListNode pNode = head;
		ListNode clonedHead = null;
		ListNode clonedNode = null;

		if (pNode != null) {
			clonedHead = pNode.next;
			clonedNode = pNode.next;
			pNode.next = clonedNode.next;
			pNode = pNode.next;
		}

		while (pNode != null) {
			clonedNode.next = pNode.next;
			clonedNode = clonedNode.next;
			pNode.next = clonedNode.next;
			pNode = pNode.next;
		}

		return clonedHead;
	}
}

15.在 O(1) 时间内删除链表结点

问题描述：

给定单向链表的头指针和一个结点指针，定义一个函数在 O(1) 时间内删除该结点。

思路：

1. 要删除结点 i，把 i 的下一个结点 j 的内容复制到 i；
2. 把 i 的指针指向结点 j 的下一个结点；
3. 删除结点 j。其效果刚好是 i 被删除了。
4. 问题：
   • 如果待删除的是链表尾结点，它没有下一个结点。
   • 注意链表中只有一个结点，要删除头结点/尾结点，返回 null。

代码：

public static void deleteNode(Node head, Node toBeDeleted) {
	if (head == null || toBeDeleted == null) {
		return;
	}
	//要删除的不是尾结点
	if (toBeDeleted.next != null) {
		Node nex = toBeDeleted.next;
		// 把 i 的下一个结点 j 的内容复制到 i
		toBeDeleted.value = nex.value;
		// 把 i 的指针指向结点 j 的下一个结点
		toBeDeleted.next = nex.next;
	}
	//链表只有一个结点，删除头结点
	else if (head == toBeDeleted) {
		toBeDeleted = null;
		head = null;
		return null;
	}
	//链表有多个结点，待删的是尾结点
	else {
		Node node = head;
		while (node.next != toBeDeleted) {
			node = node.next;
		}
		node.next = null;
		toBeDeleted = null;
	}
	return head;
}