doyoo_C
doyoo.C
2020-04-15 18:19

双向链表反转问题(c++)

  • c++
    void reverse() {
        node* pre = NULL;
        node* next = NULL;
        node* current = header->next;
        while (current != NULL) {
            next = current->next;
            current->next = pre;
            if (next == NULL) {
                header->next = current;
                current->pre = header;
                break;
            }
            pre = current;
            current->pre = next;
            current = next;
        }
    }
void reverse() {
    node* current = header->next;
    current->pre = NULL;
    while (current != NULL) {
        node* next = current->next;
        current->next = current->pre;
        if (next == NULL) {
            header->next = current;
            current->pre = header;
            break;
        }
        current->pre = next;
        current = next;
    }
}
void addbegin(int val) {
        node* temp = new node(val, header,header->next);
        header->next = temp;
    }

下面是node类的实现

class node {
public:
    int val;
    node* next;
    node* pre;
    node(){}
    node(int val, node* pre,node* next) {
        this->val = val;
        this->pre = pre;
        this->next = next;
    }
};

上面是我实现的双向链表的反转链表的方法

但是第二种实现方法存在一些问题,在addbegin方法使用以后再使用第二种
reverse方法,则链表的反转会出现错误
例:
现有链表为 1 2 3 4
addbegin(0)后为 0 1 2 3 4
再使用第二种reverse() 链表为4 3 2 1 0 4 3 2 1 0 4 3 2 1 0·······

但是如果不使用addbegin方法 则第二种方法的反转是正常的。
请问 问题出在哪里,debug半天也没有找出问题
(第一种实现是完全正确的,header为头结点)

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

1条回答

为你推荐

换一换