反转整个链表

反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
首先使用迭代的方法

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* reverseList(struct ListNode* head) {struct ListNode *prev, *cur, *next;prev = NULL;cur = head;while(cur){next = cur->next;cur->next = prev;prev = cur;cur = next;}return prev;}

然后使用递归的方法

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* reverseList(struct ListNode* head) {
if( head == NULL || head->next == NULL )return head;struct ListNode* temp = reverseList(head->next);head -> next -> next = head;head -> next =  NULL;return temp;
}

反转链表中m、n位置的链表

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
方法1：从前往后扫描链表，用pre指针指向当前元素的前一个元素，每次将当前元素的next指针指向pre，扫描至最后即可完成整个链表的反转。时间复杂度为O(n)，空间复杂度为O(1）

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {if(head == NULL || head->next == NULL || m==n) return head; //排除掉极限情况struct ListNode *left = head, *right = NULL;                //分别定义两个指针指向m节点的前节点和n节点地后节点struct ListNode *temp = head;struct ListNode *nh = (struct ListNode *)malloc(sizeof(struct ListNode));//定义虚拟新头结点newheadstruct ListNode *prev = nh, *cur = head, *next;     //分别指向前一个节点，当前节点(current)和下一个节点nh->next = head;                                               int pos = 1;                                        //pos跟踪cur的位置while(cur){if(pos <= m || pos > n){if(pos == m){                       //首先找到m处的节点，left指向m-1处地节点，保存m节点temp = cur;left = prev;}cur = cur->next;pos++;prev = prev->next;}else{                                  //然后遍历m-n，反转m-n的节点if(pos == n){                       //找到n节点，n+1用right指向,然后组成新的链表right = cur->next;left->next = cur;temp->next = right;nh->next = cur;                //对于m=1的情况，保存新的头节点}           next = cur->next;cur->next = prev;prev = cur;cur = next;  pos++;}}if(1 == m){return nh->next;}return head;
}

方法2：插入法【特别巧妙】。例如，我们要反转1->2->3->4->5的位于[2,4]之间的元素，我们可以依次将3和4向前插入，插入3之后变为1->3->2->4->5，再插入4变为1->4->3->2->5。

 /*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {if(head == NULL || head->next == NULL || m==n) return head; //排除掉极限情况struct ListNode *left = head, *right = NULL;                //分别定义两个指针指向m节点的前节点和n节点地后节点struct ListNode *nh = (struct ListNode *)malloc(sizeof(struct ListNode));                                 //定义一个虚拟的新的头节点newheadstruct ListNode *prev = nh, *cur = head, *next;             //prev，cur, next分别指向前一个节点，当前节点和下一个节点int pos = 1;                                                //pos跟踪cur的位置nh->next = head;                                            //新的链表while(cur && pos < m){prev = prev->next;cur = cur->next;pos++;}left = prev;int i = n-m;while(i--){next = cur->next;cur->next = next->next;next->next = left->next;left->next = next;    }return nh->next;}