给定一个链表的头结点指针, 目标是翻转这个链表。
例子:
Input : Head of following linked list
1->2->3->4->NULL
Output : Linked list should be changed to,
4->3->2->1->NULL
Input : Head of following linked list
1->2->3->4->5->NULL
Output : Linked list should be changed to,
5->4->3->2->1->NULL
Input : NULL
Output : NULL
Input : 1->NULL
Output : 1->NULL
迭代方法
利用3个指针，prev 为 NULL, curr 等于头结点，next 为 NULL.
遍历整个链表。在循环体内, 这样做。
// Before changing next of current,
// next node
next = curr->next
// This is where actual reversing happens
curr->next = prev
// Move prev and curr one step forward
prev = curr
curr = next
循环第一步结束, i.e., 在 next = curr->next 之后
循环一次之后
// Iterative C program to reverse a linked list
#include<stdio.h>
#include<stdlib.h>
/* Link list node */
struct Node
{
int data;
struct Node* next;
};
/* Function to reverse the linked list */
static void reverse(struct Node** head_ref)
{
struct Node* prev = NULL;
struct Node* current = *head_ref;
struct Node* next = NULL;
while (current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head_ref = prev;
}
/* Function to push a node */
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Function to print linked list */
void printList(struct Node *head)
{
struct Node *temp = head;
while(temp != NULL)
{
printf("%d ", temp->data);
temp = temp->next;
}
}
/* Driver program to test above function*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 15);
push(&head, 85);
printf("Given linked list\n");
printList(head);
reverse(&head);
printf("\nReversed Linked list \n");
printList(head);
getchar();
}
###
所给链表
85 15 4 20
翻转后的链表
20 4 15 85
时间复杂度: O(n)
空间复杂度: O(1)
递归方法:
1) 把链表划分为2部分 - 第一个结点和剩下的结点
2) 对剩下的链表调用翻转方法.
3) 把剩下的链表链接到第一个结点.
4) 固定头指针
void recursiveReverse(struct Node** head_ref)
{
struct Node* first;
struct Node* rest;
/* empty list */
if (*head_ref == NULL)
return;
/* suppose first = {1, 2, 3}, rest = {2, 3} */
first = *head_ref;
rest = first->next;
/* List has only one node */
if (rest == NULL)
return;
/* reverse the rest list and put the first element at the end */
recursiveReverse(&rest);
first->next->next = first;
/* tricky step -- see the diagram */
first->next = NULL;
/* fix the head pointer */
*head_ref = rest;
}
时间复杂度: O(n)
空间复杂度: O(1)
一个更简单的方法
下面的方法用 C++ 实现。
// A simple and tail recursive C++ program to reverse
// a linked list
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int data;
struct Node *next;
};
void reverseUtil(Node *curr, Node *prev, Node **head);
// This function mainly calls reverseUtil()
// with prev as NULL
void reverse(Node **head)
{
if (!head)
return;
reverseUtil(*head, NULL, head);
}
// A simple and tail recursive function to reverse
// a linked list. prev is passed as NULL initially.
void reverseUtil(Node *curr, Node *prev, Node **head)
{
/* If last node mark it head*/
if (!curr->next)
{
*head = curr;
/* Update next to prev node */
curr->next = prev;
return;
}
/* Save curr->next node for recursive call */
node *next = curr->next;
/* and update next ..*/
curr->next = prev;
reverseUtil(next, curr, head);
}
// A utility function to create a new node
Node *newNode(int key)
{
Node *temp = new Node;
temp->data = key;
temp->next = NULL;
return temp;
}
// A utility function to print a linked list
void printlist(Node *head)
{
while(head != NULL)
{
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
// Driver program to test above functions
int main()
{
Node *head1 = newNode(1);
head1->next = newNode(2);
head1->next->next = newNode(3);
head1->next->next->next = newNode(4);
head1->next->next->next->next = newNode(5);
head1->next->next->next->next->next = newNode(6);
head1->next->next->next->next->next->next = newNode(7);
head1->next->next->next->next->next->next->next = newNode(8);
cout << "Given linked list\n";
printlist(head1);
reverse(&head1);
cout << "\nReversed linked list\n";
printlist(head1);
return 0;
}
###
Output:
Given linked list
1 2 3 4 5 6 7 8
Reversed linked list
8 7 6 5 4 3 2 1