如何在不影响原链表的情况下反转链表?

huangapple go评论160阅读模式
英文:

How to reverse a linked list without affecting the original one?

问题

  1. 我想反转一个链表,我写了以下基本程序: -

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;
}

  1. 这是打印链表的程序
  1. public void print(ListNode curr){
  2. while(curr!=null){
  3. System.out.print(curr.val+" ");
  4. curr = curr.next;
  5. }
  6. System.out.println();
  7. }
  1. 现在我的列表是[1,2,21]
  2. 当我打印输出时,如下所示

1 2 3 1

  1. 当我反转它并打印头部和反转后的输出如下: -

ListNode reversed = reverseList(head);
print(head);
print(reversed)

  1. **输出**

1
1 3 2 1

  1. 有人可以解释如何保持头部不变吗?
  2. 我尝试反转链表。我成功了,但在反转列表后,它改变了我的当前列表。我想保持它不变。
英文:

I want to reverse a LinkedList, I wrote the basic program as follows: -

  1. public class ListNode{
  2. int val;
  3. ListNode next;
  4. ListNode(){}
  5. ListNode(int val){this.val = val;}
  6. ListNode(int val, ListNode next){this.val = val; this.next = next;}
  7. }
  1. public ListNode reverseList(ListNode head) {
  2. ListNode prev = null;
  3. ListNode curr = head;
  4. while(curr!=null){
  5. ListNode next = curr.next;
  6. curr.next = prev;
  7. prev = curr;
  8. curr = next;
  9. }
  10. return prev;
  11. }

Here is the program to print the LinkedList

  1. public void print(ListNode curr){
  2. while(curr!=null){
  3. System.out.print(curr.val+" ");
  4. curr = curr.next;
  5. }
  6. System.out.println();
  7. }

Now my list is [1,2,21]

when I print it output is as follows

  1. 1 2 3 1

when I reverse it and print head and reversed the output is as follows: -

  1. ListNode reversed = reverseList(head);
  2. print(head);
  3. print(reversed)

Output

  1. 1
  2. 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

这听起来像一个课程项目。

尝试这样做:

  1. 运行原始列表并将每个值存储在栈中。当你完成原始列表时,栈(自顶向下)将包含值以相反顺序排列。
  2. 弹出栈并将值添加到新列表中。
英文:

This sounds like a class project.

Try this:

  1. 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.
  2. 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.

  1. public ListNode reverseList(ListNode head) {
  2. ListNode reversed = null;
  3. ListNode curr = head;
  4. while (curr != null) {
  5. reversed = new ListNode(curr.val, reversed);
  6. curr = curr.next;
  7. }
  8. return reversed;
  9. }

huangapple
  • 本文由 发表于 2023年4月10日 19:12:50
  • 转载请务必保留本文链接:https://go.coder-hub.com/75976574.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定