本文共 1252 字，大约阅读时间需要 4 分钟。
题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。
边界条件：
head为空，只有一个结点，只有两个结点，超过3个结点。
思路：
可以用三个指针来指向连续地3个结点，然后让第二个指针的next指向第一个指针，在将3个指针往后移动，这样只需遍历一次链表，就可以实现链表反转。
时间复杂度：O(n)
#include如果用递归方法做，更简单：#include #include #include #include using namespace std;struct ListNode{ int value; ListNode *next; ListNode(int a){ value = a; next = NULL; }};ListNode *ReverseList(ListNode *head){ if (head == NULL || head->next == NULL) return head; ListNode* p1 = head, *p2 = head->next, *p3 = p2->next; while (p3 != NULL) { p2->next = p1; p1 = p2; p2 = p3; p3 = p3->next; } p2->next = p1; head->next = NULL; return p2;}int main(){ ListNode *a1 = new ListNode(1); ListNode *a2 = new ListNode(2); ListNode *a3 = new ListNode(3); ListNode *a4 = new ListNode(4); ListNode *a5 = new ListNode(5); a1->next = a2; a2->next = a3; a3->next = a4; a4->next = a5; ListNode *re = ReverseList(a1); for (; re != NULL; re = re->next) cout << re->value << " "; cout << endl; return 0;}
ListNode *ReverseListByRecursive(ListNode *head){ if (head==NULL||head->next == NULL) return head; ListNode *newNode = ReverseListByRecursive(head->next); head->next->next = head; head->next = NULL; return newNode;} 转载地址：http://vapmi.baihongyu.com/