双向链表中含有数据成员_data,_prev,_next,也就是说数据节点前后都有一个指向前一个节点和后一个节点的指针。然而要想实现双向链表的逆置,首先我们先来了解一下单链表的逆置

        单链表的逆置,所采用的方法是头插法,所谓的头插法就是新建一个NewHead指针,这个指针永远指向新的链表的头节点_head,然后从原链表中“摘取”节点连接到新的链表上,以下是c++代码实现:

void Resever()    {        ListNode* cur = _head;        ListNode* tmp = cur;        ListNode* NewHead = NULL;        while (cur)        {            tmp = cur;            cur = cur->_next;            tmp->_next = NewHead;            NewHead = tmp;        }        _head = NewHead;    }

      上述的“摘取”就是将头节点与链表断开,与新链表链接。cur节点与原链表断开时要记得保存cur->next节点,所以新建一个临时变量tmp存储起来。

       对照单链表的逆置我们就可以写出爽链表的逆置的第一种实现方法,后面还有更加简便的方法。

void Resever()    {        ListNode* cur = _head;        ListNode* tmp = cur;        ListNode* NewHead = NULL;        while (cur)        {            tmp = cur;            cur = cur->_next;            tmp->_next = NewHead;            tmp->_prev = cur;            NewHead = tmp;        }        _head = NewHead;    }

     这种方法实现起来和单链表一样,只是多了tmp->_prev = cur;这一个语句,下面是实现的第二种方法:

void Resever()    {        ListNode* begin = _head;        ListNode* end = _tail;        while (begin != end && begin->_prev != end)        {            swap(begin->_data, end->_data);            begin = begin->_next;            end = end->_prev;        }     }

     这种方法的核心思想就是只交换节点中的数据成员_data,其他的前后指针不变,这种方法也是比较简便的。但是要注意while语句的循环条件while (begin != end && begin->_prev != end),找到了这两种情况就可以成功达到结束条件。下面还有一种也是比较方便的方法:

void Resever()    {        ListNode* cur = _head;        swap(_head, _tail);        while (cur)        {            swap(cur->_prev, cur->_next);            cur = cur->_prev;        }    }

     这种方法是不是看起来要更加简便一点呢。这种方法就是先交换头尾指针,然后逐个交换节点的前指针和后指针,达到逆置的效果。