用Java实现在原链表上进行翻转
时间: 2023-06-19 19:04:17 浏览: 61
可以通过迭代和递归两种方法实现在原链表上进行翻转。
迭代方法:
```java
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
```
递归方法:
```java
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode p = reverseList(head.next);
head.next.next = head;
head.next = null;
return p;
}
```
以上两种方法都可以实现在原链表上进行翻转,时间复杂度均为 O(n),空间复杂度均为 O(1)。
相关问题
用Java实现反转链表起⽹络
反转链表是一个常见的面试题,以下是用Java实现反转链表的代码:
```java
class Node {
int val;
Node next;
public Node(int val) {
this.val = val;
this.next = null;
}
}
class ReverseLinkedList {
Node head;
public ReverseLinkedList() {
head = null;
}
public void insert(int val) {
if (head == null) {
head = new Node(val);
return;
}
Node curr = head;
while (curr.next != null) {
curr = curr.next;
}
curr.next = new Node(val);
}
public void reverse() {
Node prev = null;
Node curr = head;
Node next = null;
while (curr != null) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
head = prev;
}
public void printList() {
Node curr = head;
while (curr != null) {
System.out.print(curr.val + " ");
curr = curr.next;
}
System.out.println();
}
}
```
这里定义了一个Node类和ReverseLinkedList类,Node类表示链表中的节点,ReverseLinkedList类表示链表。insert方法用于插入节点,reverse方法用于反转链表,printList方法用于打印链表。reverse方法里使用了三个指针prev、curr、next,分别表示前一个节点、当前节点和下一个节点,通过改变节点之间的链接关系,实现了反转链表的功能。
使用Java实现反转链表源码
可以使用以下Java代码实现反转链表: public class ReverseLinkedList {
static class Node {
int val;
Node next;
Node(int val) {
this.val = val;
}
}
public static Node reverseLinkedList(Node head) {
Node prev = null;
Node current = head;
while(current != null) {
Node next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
}