一个node链表翻转的面试题

经典面试题总结,欢迎大家来留言区讨论

下面列举了两种解法:
欢迎留言讨论
一个node链表的值分别为67,0,24,58,31,请把node翻转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static class Node {
int val;
Node next = null;
Node(int val) {
this.val = val;
}
}

public static void main(String[] args) {
Node nodeFirst = new Node(67);
nodeFirst.next = new Node(0);
nodeFirst.next.next = new Node(24);
nodeFirst.next.next.next = new Node(58);
nodeFirst.next.next.next.next = new Node(31);

Node node = reverseNodeByNodeMethod(nodeFirst);
while (node != null) {
System.out.println(node.val);
node = node.next;
}
}

一种利用node自身的方法翻转.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static Node reverseNodeByNodeMethod(Node nodeFirst) {
Node currentNode = nodeFirst;
Node nextNode = null;
Node nextNextNode;
Node newFirstNode = null;
if (currentNode.next != null) {
nextNode = currentNode.next;
}
currentNode.next = null;
while (nextNode != null) {
if (nextNode.next != null) {
nextNextNode = nextNode.next;
} else {
newFirstNode = nextNode;
nextNode.next = currentNode;
break;
}
nextNode.next = currentNode;
currentNode = nextNode;
nextNode = nextNextNode;
}
return newFirstNode;
}

第二种解法,将node所有节点放入stack中,为了防止造成node内部循环,所以在stack存储之后将node.next置为null



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static Node reverseNodeByStack(Node nodeFirst) {
Stack<Node> stack = new Stack<>();
Node node = nodeFirst;
while (node.next != null) {
Node nextNode = node.next;
stack.push(node);
node.next = null;
node = nextNode;
}
Node newFirstNode = node;
while (!stack.isEmpty()) {
node.next = stack.pop();
node = node.next;
}
node.next = null;
return newFirstNode;
}
-------------感谢您的阅读祝您生活愉快!-------------

本文标题:一个node链表翻转的面试题

文章作者:小明

发布时间:2018年01月11日 - 10:01

最后更新:2018年01月19日 - 16:01

原始链接:https://www.iteway.com/2018/01/11/一个node链表翻转的面试题/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

支持一杯咖啡
0%