【数据结构】单链表（二）单链表的逆置，合并与删除

74 阅读 0 评论 49 点赞

我是靠谱客的博主满意太阳，最近开发中收集的这篇文章主要介绍【数据结构】单链表（二）单链表的逆置，合并与删除，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

接下来我们讨论下链表的一些高级操作

逆置（循环写法）：

public Node reverse(Node head) {
	Node reverseHead = null;
	Node runner = head;
	while (runner != null) {
		Node next = runner.next;
		runner.next = reverseHead;
		reverseHead = runner;
		runner = next;
	}
	return reverseHead;
}

逆置（递归写法）：

	public static Node reverseRec(Node head) {
		if(head==null)
			return head;
		return reverseRec(head, head.next);
	}

	public static Node reverseRec(Node prev, Node curr) {
		if(curr==null)
			return prev;
		Node reverseHead = reverseRec(prev.next, curr.next);
		curr.next=prev;
		prev.next=null;
		return reverseHead;
	}

合并：

	public static void merge(Node head1, Node head2) {
		while (head1 != null && head2 != null) {
			if (head1.next == null) {
				head1.next = head2;
				return;
			}
			Node next = head2.next;
			head2.next = head1.next;
			head1.next = head2;
			head1 = head2.next;
			head2 = next;
		}
	}

删除：

public void deleteNode(Node Delete) {
	if (Delete == null || Delete.next == null)
		return;
	Delete.item = Delete.next.item;
	Delete.next = Delete.next.next;
}