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

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

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

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

尝试这样做:

  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.

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

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:

确定