Description:
Reverse a linked list.
Example:
For linked list 1->2->3, the reversed linked list is 3->2->1
Link:
http://www.lintcode.com/en/problem/reverse-linked-list/
解题思路:
针对每个节点curr,只要改变该节点的next,让其指向curr前一个节点(需要用一个变量prev储存),然后再对这个节点的下个节点进行相同的操作。
这道题搞清楚以后,针对k-group那道题的反转代码就会写了。
Tips:
在进行反转操作之后,head已经不是第一个节点了而是最后一个,此时用dummy并不好用,反而直接返回prev这个点方便。
Time Complexity:
O(n),n为节点个数
完整代码:
ListNode *reverse(ListNode *head) { ListNode *temp; ListNode *curr = head; ListNode *prev = NULL; while(curr != NULL) { temp = curr->next; curr->next = prev; prev = curr; curr = temp; } return prev; }