反转链表#

递归反转链表#

递归反转链表的思想是，递归到链表末尾，再从尾至头得反转链表指针

递归的好处就是比迭代法代码量少，且更读易懂。坏处就是容易爆栈，在主流的语言中一般递归个几千层就会爆栈

首先我们需要创建一个函数，我们只需要向其传递一个值，就是指向链表头的指针

1
void Reverse(Linked* p){}

然后再判断这个指针非空，并递归到末尾

1
void Reverse(Linked* p){
2
  if(p -> next == nullptr){
3
    return;
4
  }
5
  re(p -> next)
6
}

假设我们有个一个全局变量head，那就让其指向末尾元素

1
void Reverse(Linked* p){
2
  if(p -> next == nullptr){
3
    head = p;
4
    return;
5
  }
6
  Reverse(p -> next);
7
}

随后再从后往前遍历，让后面的元素指向前面的元素

1
void Reverse(Linked* p){
2
  if(p -> next == nullptr){
3
    head = p;
4
    return;
5
  }
6
  Reverse(p -> next);
7
  Linked* q = p -> next;
8
  //定义q表示下一位元素
9
  q -> next = p;
10
  //使后面的元素指向前面的元素
11
  p -> next = nullptr;
12
  //把当前元素指针归零，如果是第一位元素则反转后不指向任何元素，如果不是则没有影响
13
}

迭代反转列表#

首先我们还是需要创建一个函数，但我们不需要往里面传递值了，直接调用全局变量就好

1
void Reverse(){}

我们需要遍历链表并反转其指针

1
void Reverse(){
2
  Linked* p = head;
3
  while(next != nullptr){
4
    p = p -> next;
5
  }
6
}

但我们发现要是直接反转链表的话，下一位元素就会丢失，并且链表也没办法传递上一位的值，所以我们需要额外的两个变量来存储上一位和下一位

1
void Reverse(){
2
  Linked* last,current,next;
3
  //分别表示上一位，这一位和下一位
4
  current = head;
5
  last = nullptr;
6
  while(current != nullptr){
7
    next = current -> next;
8
    current -> = last;
9
    last = current;
10
    current = next;
11
    //整体前移
12
  }
13
  head = last;
14
  //使头部指向末尾
15
}