0

在给定指向链表中给定节点的指针的情况下，尝试反转链表元素。例如，我将获得一个指向链表中第 4 个节点的指针和一个指向第 7 个节点的指针，并且必须反转这些节点之间的节点。这是一些不起作用的相关代码：

template <class T>
void List<T>::reverse( ListNode * & startPoint, ListNode * & endPoint ){

  if (startPoint == NULL)  
    return;

  if (startPoint->prev != NULL)
    startPoint->prev->next = endPoint;

  if (endPoint->next != NULL)
    endPoint->next->prev = startPoint;

  ListNode * curr = startPoint;
  ListNode * temp = startPoint;

  while(curr != endPoint)
  {
    temp = curr->next;
    curr->next = curr->prev;
    curr->prev = temp;
    curr = temp;
  }

  temp = endPoint->next;
  endPoint->next = endPoint->prev;
  endPoint->prev = temp; 

  temp = startPoint->next;
  startPoint->next = endPoint->next;
  endPoint->prev = startPoint->prev;

  temp = startPoint;
  startPoint = endPoint;
  endPoint = temp;

}

此代码编译但没有正确执行反向节点，我不知道为什么。

4

1 回答 1

0

我没有尝试过编码，但从算法上讲这应该很快；

1）首先从子列表的开始和结束位置之间的所有节点交换 和 的prev值next。这将反转其间所有节点的顺序。只留下边缘节点。

2）在所有位置交换下一个和上一个后，还将来自原始起始节点的更新的下一个与来自原始结束节点的更新的上一个交换。现在这些节点将指向序列的正确其余部分。

3) 用于管理也更新刚好在序列之外的节点以正确指向。

示例（节点显示为“NODE(PREV, NEXT)”）

A(0,B) - B(A,C) - C(B,D) - D(C,E) - E(D,F) - F(E,-)

反转节点 1 - 4 (B - E)

第一步： 

A(0,B) - B(C,A) - C(D,B) - D(E,C) - E(F,D) - F(E,-)

第二

A(0,B) - B(C,F) - C(D,B) - D(E,C) - E(A,D) - F(E,-)

第三

A(0,E) - B(C,F) - C(D,B) - D(E,C) - E(A,D) - F(B,-)

现在来可视化订单：

A(0,E) - E(A,D) - D(E,C) - C(D,B) - B(C,F) - F(B,-)

就是这样，颠倒了中间的 4 个节点。

于 2013-10-07T19:17:21.240 回答