ITKeyword,专注技术干货聚合推荐

注册 | 登录

算法与数据结构面试题(10)-颠倒链表

qhshiniba 分享于 2014-12-19

推荐:算法和数据结构面试题(16)-单链表倒置

题目 链表操作(1)单链表就地逆置 解题思路 关于单链表 1.创建单链表,需要首先写一个单链表的类。 模仿LinkedList写一个SingleLinkedList类。 /** * Copyrig

2020腾讯云“6.18”活动开始了!!!(巨大优惠重现!4核8G,5M带宽 1999元/3年),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1059

2020阿里云最低价产品入口,含代金券(新老用户有优惠),
地址https://www.aliyun.com/minisite/goods

题目


用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。

解题思路


1.先用递归颠倒

2.尝试不用递归颠倒


代码


1.递归式


推荐:算法与数据结构面试题(11)-一次遍历得到链表的中间节点

题目 如题 解题思路 参考 代码 public class Problem11 { LinkedListNode fast;// 每次前进两步的指针 LinkedListNode slow;// 每次前进一步的指针 public L

public class Problem8 {

	public LinkedListNode invert(LinkedListNode node) {
		if (node == null) {
			throw new NullPointerException();
		}

		LinkedListNode endNode = null;
		LinkedListNode nextNode = node.getNextNode();
		if (nextNode != null) {
			node.setNextNode(null);
			endNode = invert(nextNode);
			nextNode.setNextNode(node);
		} else {
			endNode = node;
		}

		return endNode;
	}

	public LinkedListNode parseLinkedList(int[] data) {
		LinkedListNode lastNode = null;
		for (int i = data.length - 1; i >= 0; i--) {
			LinkedListNode currentNode = new LinkedListNode();
			currentNode.setValue(data[i]);
			currentNode.setNextNode(lastNode);
			lastNode = currentNode;
		}

		return lastNode;
	}

	public static void main(String[] args) {
		int[] data = { 1, 2, 3, 4, 5, 6, 7 };
		Problem8 problem8 = new Problem8();
		LinkedListNode rootNode = problem8.parseLinkedList(data);
		LinkedListNode endNode = problem8.invert(rootNode);
		problem8.printlnLinkedArray(endNode);
		System.out.println("Done");
	}
	public void printlnLinkedArray(LinkedListNode node){
		if(node == null) return;
		System.out.println("" + node.getValue());
		printlnLinkedArray(node.getNextNode());
	}
}


输出


7
6
5
4
3
2
1
Done


2.非递归式


public class Problem8_2 {
	public LinkedListNode invert(LinkedListNode node, int length) {
		LinkedListNode[] nodes = new LinkedListNode[length];
		// 先断链
		for (int i = 0; i < length; i++) {
			if (node != null) {
				nodes[i] = node;
				node = node.getNextNode();
			}
		}
		// 再指针反向

		for (int i = length - 1; i >= 0; i--) {
			if (i == 0) {
				nodes[i].setNextNode(null);
			} else {
				nodes[i].setNextNode(nodes[i - 1]);
			}
		}

		return nodes[length - 1];
	}

	public LinkedListNode parseLinkedList(int[] data) {
		LinkedListNode lastNode = null;
		for (int i = data.length - 1; i >= 0; i--) {
			LinkedListNode currentNode = new LinkedListNode();
			currentNode.setValue(data[i]);
			currentNode.setNextNode(lastNode);
			lastNode = currentNode;
		}

		return lastNode;
	}

	public static void main(String[] args) {
		int[] data = { 1, 2, 3, 4, 5, 6, 7 };
		Problem8_2 problem8 = new Problem8_2();
		LinkedListNode rootNode = problem8.parseLinkedList(data);
		LinkedListNode endNode = problem8.invert(rootNode, data.length);
		problem8.printlnLinkedArray(endNode);
		System.out.println("Done");
	}

	public void printlnLinkedArray(LinkedListNode node) {
		if (node == null)
			return;
		System.out.println("" + node.getValue());
		printlnLinkedArray(node.getNextNode());
	}

}



推荐:算法与数据结构面试题(13)-求链表倒数第K个节点

题目 题目:输入一个单向链表,输出该链表中倒数第k 个结点。链表的倒数第0 个结点为链表的尾指针。 解题思路 需要2个指针,一个是遍历指针,一个是跟随指针。

题目 用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。 解题思路 1.先用递归颠倒 2.尝试不用递归颠倒 代码 1.递归式 public class Problem8 { public LinkedListNode inv

相关阅读排行


相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。