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

qhshiniba 分享于 2014-12-19

# 题目

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

1.先用递归颠倒

2.尝试不用递归颠倒

# 代码

## 1.递归式

```public class Problem8 {

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

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

return endNode;
}

for (int i = data.length - 1; i >= 0; i--) {
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();
System.out.println("Done");
}
if(node == null) return;
System.out.println("" + node.getValue());
}
}```

```7
6
5
4
3
2
1
Done
```

## 2.非递归式

```public class Problem8_2 {
// 先断链
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];
}

for (int i = data.length - 1; i >= 0; i--) {
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();
System.out.println("Done");
}

if (node == null)
return;
System.out.println("" + node.getValue());
}

}
```

×
• 登录
• 注册

×