减去链表节点

Question

我正在尝试解决一个链表问题。给定一个单链表，修改前一半节点的值如下:

第一个节点的新值=最后一个节点的值-第一个节点的当前值

第二个节点的新值=第二个最后一个节点的值-第二个节点的当前值

的例子:

给定链表1 -> 2 -> 3 -> 4 -> 5

你应该返回4 -> 2 -> 3 -> 4 -> 5

目前我能想到的解决方案是

1. 遍历链表查找长度
2. 迭代链表的后半部分，将节点值压入堆栈
3. 迭代列表的前半部分，弹出堆栈，减去节点值。

这可能是最幼稚的解决方案。谁能在时间/空间方面提出更有效的解决方案(想要避免多次迭代和额外的堆栈空间)?提前谢谢。

答案:

public ListNode subtract(ListNode a) {
        ListNode slow =a;
        ListNode fast=a;

        ListNode head = a;
        ListNode middle = null;
        while(fast!=null && fast.next!=null)
            {
                if(fast.next.next!=null) // in case numOfNodes are even , we need to stay at middle
                    slow=slow.next;
                fast = fast.next.next;
            }
       if(slow==fast)
            return a;
       middle = slow; 
       ListNode secondHalf = middle.next;
       middle.next = null;
       ListNode reversed = reverse(secondHalf);
       ListNode  temp1  = reversed;
       while(temp1!=null ){
           head.val = temp1.val - head.val;
           temp1 = temp1.next;
           head = head.next;
       }
       middle.next = reverse(reversed);

       return a;
    }

    public ListNode reverse(ListNode head){
        ListNode current = head;
        ListNode previous = null;
        while(current!=null) {
            ListNode temp = current.next;
            current.next = previous;
            previous = current;
            current = temp;
        }
        return previous;
    }

Answer 1

如果允许修改列表，那么有一个比我在评论中提到的更好的解决方案，即使用恒定的额外空间:

1. 查找中间

2. 将列表从中间向右反转

3. 通过逐级遍历两个列表来执行减法

4. 再次将列表反向/连接以获得原始列表顺序

所有这些步骤都需要O(1)空间和O(n)时间，因此整个算法也需要O(1)空间和O(n)时间。

这只是一个算法的概要，用来证明在O(n)时间内具有恒定的额外空间是可能的，有一些陷阱，如奇数/偶数元素等。

可能有一些改进的空间，但你不能比O(n)时间更好，因为找到最后一个元素或执行减法已经需要O(n)时间。

Answer 2

你可以写一个递归函数来解决这个问题，而不需要额外的空间，也就是说，如果你不认为堆栈帧是额外的空间。

代码是用c#编写的，但您应该能够轻松地将其翻译成您需要的语言。

使用此方法需要注意的一点是，您需要使用全局变量跟踪当前节点。

static ListNode<int> temp = list.head; // Point to first element in the list
private static int reverse(ListNode<int> listNode, int currentNode, int totalNodes)
{
    if (listNode == null)
    {
        return 0;
    }
    currentNode = reverse(listNode.next, currentNode, totalNodes + 1);
    if (currentNode < totalNodes) //To check if half is reached
    {
        temp.data = listNode.data - temp.data;
        temp = temp.next;
    }
    return ++currentNode;
}

你可以像reverse(list.head, 0, 0);那样调用这个方法，忽略返回值，或者把它存储在某个地方，因为它指向链表的中间，这在以后的某个地方可能会派上用场。

使用链表的标准实现，我怀疑你是否能够实现比这更好的空间/时间复杂性。

如果您可以修改ListNode的实现以包含该节点的索引，则可以替换全局变量并将其作为参数传递。