扭转双向链接的部分（c ++）

I'm attempting to right a method which reverses a doubly linked list.

我试图找到一个反转双向链表的方法。

template <class T>
void List<T>::reverse() {
  reverse(head_, tail_);
}

template <class T>
void List<T>::reverse(ListNode*& startPoint, ListNode*& endPoint) {
  if(startPoint == NULL || endPoint == NULL) return;

  ListNode* currPoint = *&startPoint;
  ListNode* end = endPoint->next;

  while(currPoint != end ) {
    ListNode* tmp = currPoint->next;
    currPoint->next = currPoint->prev;
    currPoint->prev = tmp;

    if(tmp == end) {
      endPoint = startPoint;
      startPoint = currPoint;
    }

    currPoint = tmp;
  }
}

So, head_ and tail_ are the pointers to the beginning and end of the DLL. The actual process of reversing the list should be fairly simple - reverse the prev and next pointer for every ListNode in the sequence.

因此,head_和tail_是指向DLL开头和结尾的指针。反转列表的实际过程应该相当简单 - 反转序列中每个ListNode的prev和next指针。

As you can see, I'm attempting to make it so that the second method can reverse any sub-part of the DLL. I'll be using the second method in other methods, but for now my only goal is to make it work for reversing the entire list. I think that the biggest issue is that head_ isn't being updated appropriately, since nothing is present in the when I print the list.

正如您所看到的,我正在尝试使第二种方法可以反转DLL的任何子部分。我将在其他方法中使用第二种方法,但是现在我唯一的目标是让它可以反转整个列表。我认为最大的问题是head_没有得到适当的更新,因为当我打印列表时没有任何内容。

When I print my fairly basic test it simply shows:

当我打印我相当基本的测试时,它只显示:

Expected:   < 9 8 7 6 5 4 3 2 1 0 >
Actual:     < >

One implementation was showing the "9" in the actual output, but I'm fairly certain that was because the first portion of the list was simply being thrown away.

一个实现在实际输出中显示“9”,但我很确定这是因为列表的第一部分被丢弃了。

1 个解决方案

#1

You can simplify the problem into three steps :

您可以将问题简化为三个步骤:

Store prev of startpoint and next of endpoint, and make them point to nullptr.

存储起点和终点的下一个,并使它们指向nullptr。

Reverse the sublist using the same approach which is used for a full length of linked list.

使用与链接列表的完整长度相同的方法反转子列表。

Connect start and end nodes of reversed sublist with the stored values in step 1.

将反向子列表的开始和结束节点与步骤1中存储的值相连。

This way

[prev] startpoint  ... endpoint [nxt]

[prev]   (nullptr) startpoint... endpoint (nullptr)   [nxt]

[prev]   (nullptr) reverse(startpoint...endpoint) (nullptr)   [nxt]

[prev] begin(reversed-sublist) ...end(reversed-sublist)  [nxt]

#1