java创建一个单向链表并添加5个元素并用两种方式实现顺序表的逆置
时间: 2023-06-02 11:08:02 浏览: 68
很高兴与您进行交流。对于您的问题,我很愿意为您解答。
首先,关于单向链表的创建与元素添加,示例代码如下:
```java
class Node {
int val;
Node next;
Node(int val) {
this.val = val;
}
}
public class LinkedListDemo {
public static void main(String[] args) {
Node head = new Node(1);
Node cur = head;
for (int i = 2; i <= 5; i++) {
cur.next = new Node(i);
cur = cur.next;
}
}
}
```
以上代码创建了一个包含 5 个节点的单向链表,其中 head 节点为头结点,cur 节点为当前节点,用来指向链表中的最后一个节点。
接着,关于实现顺序表的逆置,我们可以分别使用迭代和递归两种方式:
1、迭代方式实现:
```java
public static void reverseIteratively(Node head) {
if (head == null || head.next == null) {
return;
}
Node prev = null;
Node cur = head;
while (cur != null) {
Node next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
}
```
以上代码使用了三个指针,prev 指向当前节点的前一个节点,cur 指向当前节点,next 指向当前节点的后一个节点。每次将当前节点指向其前一个节点,然后将三个节点分别向后移动一个节点,直到 cur 节点指向尾节点为止。
2、递归方式实现:
```java
public static Node reverseRecursively(Node head) {
if (head == null || head.next == null) {
return head;
}
Node newHead = reverseRecursively(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
```
以上代码使用了递归的方式,首先判断头结点是否为空或只包含一个节点,若是则直接返回头结点。然后使用递归获取链表中的最后一个节点,将其赋值给 newHead。最后将当前节点的后一个节点指向当前节点,然后将当前节点的 next 指针置为 null,然后返回 newHead。
希望以上解答能帮助到您,如果您还有其他问题,请继续提问。