英文:
How to reverse a linked list without affecting the original one?
问题
我想反转一个链表,我写了以下基本程序: -
public class ListNode{
int val;
ListNode next;
ListNode(){ }
ListNode(int val){this.val = val; }
ListNode(int val, ListNode next){this.val = val; this.next = next; }
}
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while(curr!=null){
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
这是打印链表的程序
public void print(ListNode curr){
while(curr!=null){
System.out.print(curr.val+" ");
curr = curr.next;
}
System.out.println();
}
现在我的列表是[1,2,21]
当我打印输出时,如下所示
1 2 3 1
当我反转它并打印头部和反转后的输出如下: -
ListNode reversed = reverseList(head);
print(head);
print(reversed)
**输出**
1
1 3 2 1
有人可以解释如何保持头部不变吗?
我尝试反转链表。我成功了,但在反转列表后,它改变了我的当前列表。我想保持它不变。
英文:
I want to reverse a LinkedList, I wrote the basic program as follows: -
public class ListNode{
int val;
ListNode next;
ListNode(){}
ListNode(int val){this.val = val;}
ListNode(int val, ListNode next){this.val = val; this.next = next;}
}
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while(curr!=null){
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
Here is the program to print the LinkedList
public void print(ListNode curr){
while(curr!=null){
System.out.print(curr.val+" ");
curr = curr.next;
}
System.out.println();
}
Now my list is [1,2,21]
when I print it output is as follows
1 2 3 1
when I reverse it and print head and reversed the output is as follows: -
ListNode reversed = reverseList(head);
print(head);
print(reversed)
Output
1
1 3 2 1
Can someone explain how to keep head unchanged?
I tried to reverse the linked list. I was successful but after reversing the list , it altered my current list. I want to keep it unchanged.
答案1
得分: 0
这听起来像一个课程项目。
尝试这样做:
- 运行原始列表并将每个值存储在栈中。当你完成原始列表时,栈(自顶向下)将包含值以相反顺序排列。
- 弹出栈并将值添加到新列表中。
英文:
This sounds like a class project.
Try this:
- Run the original list and store each value on a stack.
When you finish the original list the stack (top down) will contain the values
in reverse order. - pop the stack and add the values to a new list.
答案2
得分: 0
public ListNode reverseList(ListNode head) {
ListNode reversed = null;
ListNode curr = head;
while (curr != null) {
reversed = new ListNode(curr.val, reversed);
curr = curr.next;
}
return reversed;
}
英文:
As @tgdavies already commented, you need to build a new list from scratch.
Walk through the original list from head to tail,
and while walking build the reversed list from tail to head.
public ListNode reverseList(ListNode head) {
ListNode reversed = null;
ListNode curr = head;
while (curr != null) {
reversed = new ListNode(curr.val, reversed);
curr = curr.next;
}
return reversed;
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论