反转链表

迭代法

1. 初始化三个指针prev为NULL，curr为head，next为NULL。
2. 通过链表迭代。在循环中，执行以下操作。
   //在更改当前节点的下一个节点之前，
   //存储下一个节点
   next = curr-> next
   //现在改变当前节点的下一节点
   //这是实际逆转发生的地方
   curr-> next = prev
   //将prev和curr向前移动一步
   prev = curr
   curr = next

总结为：先存储当前节点的下一节点，再反转当前节点的pnext指针，最后重置head头部。
注意：若head指向Null而不放数据，则prev、curr、next应相应改变

​
class Link:
    def __init__(self):
        self.phead = None
        self.length = 0

    def creat(self, datas):
        self.phead = Node(None)     # 创建空的头部，不存数据
        pend = self.phead           # 借用临时量，方便后续操作
        for i in datas:             # 依次从所给入参中拿数据
            node = Node(i)          # 创建节点
            pend.pnext = node       # 上一节点的pnext指针，指向这个新创建的节点
            pend = node             # 这个节点赋值给临时量，方便进行下一轮循环
            self.length += 1        # 链表长度+1
        pend.pnext = None           # 末尾节点的pnxet指针为空，表示后面无数据
        return self.phead           # 返回生成的链表的头指针

    def display(self):
        cursor = self.phead.pnext     # 定位到第一个节点
        for i in range(self.length):  # 根据长度判断是否到末尾
            print(cursor.data, end=' ')        # 输出节点数据
            cursor = cursor.pnext     # 指向下一节点
        print()

    def reverse(self):
        prev = self.phead               # 上一指针
        curr = self.phead.pnext         # 当前指针
        next = self.phead               # 下一指针
        while curr:
            next = curr.pnext           # 先存储下一节点
            curr.pnext = prev           # 反转pnext指针指向
            prev = curr                 # 反转完成后，上一节点后移
            curr = next                 # 反转完成后，当前节点后移
        self.phead.pnext = prev         # 重置节点

if __name__ == '__main__':
    link = Link()              # 实例化链表Link
    new = link.creat([1,2,3,4,5,6])
    link.display()
    link.reverse()
    link.display()

# Output：
# 1 2 3 4 5 6 
# 6 5 4 3 2 1 

递归方法：

1）将列表分为两部分 - 第一节点和
其余的链表。
2）对链表的其余部分进行反向调用。
3）将休息链接到第一个。
4）修复头指针

// Recursive C++ program to reverse 
// a linked list 
#include <iostream> 
using namespace std; 

/* Link list node */
struct Node { 
    int data; 
    struct Node* next; 
    Node(int data) 
    { 
        this->data = data; 
        next = NULL; 
    } 
}; 

struct LinkedList { 
    Node* head; 
    LinkedList() 
    { 
        head = NULL; 
    } 

    Node* reverse(Node* head) 
    { 
        if (head == NULL || head->next == NULL) 
            return head; 

        /* reverse the rest list and put  
          the first element at the end */
        Node* rest = reverse(head->next); 
        head->next->next = head; 

        /* tricky step -- see the diagram */
        head->next = NULL; 

        /* fix the head pointer */
        return rest; 
    } 

    /* Function to print linked list */
    void print() 
    { 
        struct Node* temp = head; 
        while (temp != NULL) { 
            cout << temp->data << " "; 
            temp = temp->next; 
        } 
    } 

    void push(int data) 
    { 
        Node* temp = new Node(data); 
        temp->next = head; 
        head = temp; 
    } 
}; 

/* Driver program to test above function*/
int main() 
{ 
    /* Start with the empty list */
    LinkedList ll; 
    ll.push(20); 
    ll.push(4); 
    ll.push(15); 
    ll.push(85); 

    cout << "Given linked list\n"; 
    ll.print(); 

    ll.head = ll.reverse(ll.head); 

    cout << "\nReversed Linked list \n"; 
    ll.print(); 
    return 0; 
} 

更简单和尾递归方法

# Node class  
class Node: 

    # Constructor to initialize the node object 
    def __init__(self, data): 
        self.data = data 
        self.next = None

class LinkedList: 

    # Function to initialize head 
    def __init__(self): 
        self.head = None


    def reverseUtil(self, curr, prev): 

        # If last node mark it head 
        if curr.next is None : 
            self.head = curr  

            # Update next to prev node 
            curr.next = prev 
            return 

        # Save curr.next node for recursive call 
        next = curr.next

        # And update next  
        curr.next = prev 

        self.reverseUtil(next, curr)  


    # This function mainly calls reverseUtil() 
    # with previous as None 
    def reverse(self): 
        if self.head is None: 
            return 
        self.reverseUtil(self.head, None) 


    # Function to insert a new node at the beginning 
    def push(self, new_data): 
        new_node = Node(new_data) 
        new_node.next = self.head 
        self.head = new_node 

    # Utility function to print the linked LinkedList 
    def printList(self): 
        temp = self.head 
        while(temp): 
            print temp.data, 
            temp = temp.next


# Driver program 
llist = LinkedList() 
llist.push(8) 
llist.push(7) 
llist.push(6) 
llist.push(5) 
llist.push(4) 
llist.push(3) 
llist.push(2) 
llist.push(1) 

print "Given linked list"
llist.printList() 

llist.reverse() 

print "\nReverse linked list"
llist.printList()