链表是一种简单但引人入胜的数据结构，可用于存储线性连接的非连续数据。

使用链接列表时，我们经常会遇到有趣的操作问题，因为它们需要开箱即用的思维方式，并且具有单链接列表的有限属性。

在本文中，我们将讨论反向链接单链列表的问题。

反向链接列表

让我们直接深入讨论该解决方案。
我们将讨论两种方法：

• 迭代解决方案(使用3个指针)
• 递归解决方案(使用伪2指针)

注意：建议您尝试解决问题，然后再寻求解决方案。

使用迭代解决方案反向链接列表

• 让我们先克服基本情况。
  如果链表只有0个节点或者只有1个节点，那么反转链表是没有意义的，因此我们可以简单地返回then and there。

• 假设现在有> = 2个节点，我们可以执行以下操作。

• 在上一个节点，当前节点，下一个节点上保留3个指针。

• 最初，将前一个节点指定为NULL，将当前节点指定为头，然后将下一个节点指定为头的后继。

• 反向上一个节点与当前节点之间的链接。

• 通过执行以下操作将所有指针向前移动：上一个节点=当前节点

• 当前节点=下一个节点

• 下一个节点=下一个节点->下一个

• 转到步骤5，直到当前节点不为NULL。

• 将head分配为上一个节点并返回。

遵循此范例的代码可在此处找到。

C语言代码

#include<stdio.h>
#include<stdlib.h>

struct node{
int data;
struct node *next;
} *head = NULL;

struct node *make_node(int data){
struct node *new = (struct node *)malloc(sizeof(struct node));
new->next = NULL; new->data = data;
return new;
}

void push(int data){
struct node *new_node = make_node(data);
new_node->next = head;
head = new_node;
}

void print_list(){
struct node *cur = head;
while(cur){
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}

void reverse_list(){
if(head == NULL || head->next == NULL)
return;
struct node *prev = NULL, *cur = head, *next;
while(cur){
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
head = prev;
}

int main(){

push(3);
push(4);
push(5);
push(6);

printf("Given Linked list is: ");
print_list();

reverse_list();

printf("Reversed Linked list is: ");
print_list();

return 0;
}

Python代码

class Node:

  def __init__(self, data):
      self.data = data
      self.next = None

class LinkedList:

  def __init__(self):
      self.head = None

  def reverse(self):
      if self.head is None or self.head.next is None:
          return

      prev = None
      cur = self.head

      while cur:
          next_element = cur.next
          cur.next = prev
          prev = cur
          cur = next_element

      self.head = prev

  def push(self, data):
      new_node = Node(data)
      new_node.next = self.head
      self.head = new_node

  def print_list(self):
      cur = self.head
      l1 = []
      while cur:
          l1.append(cur.data)
          cur = cur.next
      return l1

head = LinkedList()
head.push(3)
head.push(4)
head.push(5)
head.push(6)
print("Given list is: ", head.print_list())
head.reverse()
print("Reversed list is: ", head.print_list())

使用递归解决方案反向链接列表

递归解决方案使用更自然且易于理解的算法，因此稍微易于理解。
但是，迭代和递归解决方案的工作方式相似。

我们主要使用递归来替换指针" next"，因为我们可以递归到链表的末尾，并按照与迭代解决方案类似的方式进行操作。

唯一的区别是，由于使用了递归，我们在移至列表末尾后也向后移动。

另外，请注意，在递归解决方案中，我们不需要下一个指针，因为递归允许我们在链接列表中前进。

其中我们分为两部分来定义递归解决方案：

• 递归案例：我们首先要在链接列表中前进。

• 递归结束后，我们可以简单地将当前节点链接到上一个节点。

• 基本情况：如果当前元素为NULL，则在这种情况下，我们可以简单地将head分配为前一个节点，即链表的最后一个节点。

遵循此范例的代码可以在这里找到：

C语言代码

#include<stdio.h>
#include<stdlib.h>

struct node{
int data;
struct node *next;
} *head = NULL;

struct node *make_node(int data){
struct node *new = (struct node *)malloc(sizeof(struct node));
new->next = NULL; new->data = data;
return new;
}

void push(int data){
struct node *new_node = make_node(data);
new_node->next = head;
head = new_node;
}

void print_list(){
struct node *cur = head;
while(cur){
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}

struct node *reverse_list(struct node *prev, struct node *cur){
if(cur == NULL){
head = prev;
}
else{
reverse_list(cur, cur->next);
cur->next = prev;
}
}

int main(){

push(3);
push(4);
push(5);
push(6);

printf("Given Linked list is: ");
print_list();

reverse_list(NULL, head);

printf("Reversed Linked list is: ");
print_list();

return 0;
}

Python代码

class Node:

  def __init__(self, data):
      self.data = data
      self.next = None

class LinkedList:

  def __init__(self):

      self.head = None

  def _reverse(self, prev, cur):

      if cur is None:
          self.head = prev

      else:
          self._reverse(cur, cur.next)
          cur.next = prev

  def reverse(self):

      self._reverse(None, self.head)

  def push(self, data):

      new_node = Node(data)
      new_node.next = self.head
      self.head = new_node

  def print_list(self):

      cur = self.head
      l1 = []
      while cur:
          l1.append(cur.data)
          cur = cur.next
      return l1

head = LinkedList()
head.push(3)
head.push(4)
head.push(5)
head.push(6)
print("Given list is: ", head.print_list())
head.reverse()
print("Reversed list is: ", head.print_list())