[Leetcode]Reverse Linked List-再写单链表反转

Leetcode碰巧又出现这个问题，看来面试算法这个是很常见的题型，不过很久没写过，这次写来又花了不少时间，

主要耽搁在思想的选择上：

一是想通过遍历时直接将指针反转，这样比较高效，但是需要处理好前后指针及后续的关系；

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* reverseList(struct ListNode* head) {struct ListNode *pre = NULL;struct ListNode *p = head;while(p){struct ListNode *tmpNext = p->next;//current next nodep->next = pre;pre = p;p = tmpNext;		}return pre;
}

二是通过构建一个新的链表头，然后遍历时直接将链表元素加入到新链接中，该算法比较简明；

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* reverseList(struct ListNode* head) {struct ListNode newListHead = {0, NULL};struct ListNode *p = head;//first nodewhile(p){		struct ListNode *tmpnew = newListHead.next;struct ListNode *tmp = p->next;newListHead.next = p;p->next = tmpnew;p = tmp;}return newListHead.next;
}

三是使用递归遍历链表至倒数第二位元素，接着依次将next指针反转：

/*** 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* p = reverseList(head->next);head->next->next = head;head->next = NULL;return p;
}