206. Reverse Linked List
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
方法一：就地反转法，C语言
Runtime: 8 ms, faster than 8.37% of C online submissions for Reverse Linked List.
Memory Usage: 4.8 MB, less than 0.93% of C online submissions for Reverse Linked List.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {
if(head==NULL)
return head;
struct ListNode *dummy = (struct ListNode*)
malloc(sizeof(struct ListNode));
dummy->val = -1;
dummy->next = head;
struct ListNode* pre = dummy->next;
struct ListNode* cur = pre->next;
while(cur!=NULL){
pre->next = cur->next;
cur->next = dummy->next;
dummy->next = cur;
cur = pre->next;
}
return dummy->next;
}
方法二：C语言: 新建一个节点的指针dummy==NULL，并且用tmp指针保存head指向的下一个节点的指针, 然后将Node1指向dummy，接着让dummy移动到head
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* dummy=NULL;
while(head){
struct ListNode* tmp= head->next;
head->next = dummy;
dummy= head;
head = tmp;
}
return dummy;
}
方法三：C语言，递归
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* helper(struct ListNode* pre,
struct ListNode* cur) {
struct ListNode* tmp;
if (cur==NULL){
return pre;
}else{
tmp = cur->next;
cur->next = pre;
return(helper(cur, tmp));
}
}
struct ListNode* reverseList(struct ListNode* head) {
return (helper(NULL, head));
}
方法四：C语言递归
递归解法的思路是，不断的进入递归函数，直到head指向倒数第二个节点，因为head指向空或者是最后一个结点都直接返回了，rst则指向对head的下一个结点调用递归函数返回的头结点，此时rst指向最后一个结点，然后head的下一个结点的next指向head本身，这个相当于把head结点移动到末尾的操作，因为是回溯的操作，所以head的下一个结点总是在上一轮被移动到末尾了，但head之后的next还没有断开，所以可以顺势将head移动到末尾，再把next断开，最后返回rst即可，代码如下：
The recursive version is slightly trickier and the key is to work backwards. Assume that the rest of the list had already been reversed, now how do I reverse the front part? Let's assume the list is: n1 → … → nk-1 → nk → nk+1 → … → nm → Ø
Assume from node nk+1 to nm had been reversed and you are at node nk.
n1 → … → nk-1 → nk → nk+1 ← … ← nm
We want nk+1’s next node to point to nk.
So,
nk.next.next = nk;
Be very careful that n1's next must point to Ø. If you forget about this, your linked list has a cycle in it. This bug could be caught if you test your code with a linked list of size 2.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {
if(!head || !head->next)
return head;
struct ListNode* rst = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return rst;
}
LintCode. 0035
Java 版
/**
* Definition for ListNode
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* @param head: n
* @return: The new head of reversed linked list.
*/
public ListNode reverse(ListNode head) {
if(head==null)
return head;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy.next;
ListNode cur = pre.next;
while(cur!=null){
pre.next = cur.next;
cur.next = dummy.next;
dummy.next = cur;
cur = pre.next;
}
return dummy.next;
}
}
九章算法官方的解答
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/
public class Solution {
/**
* @param head: The head of linked list.
* @return: The new head of reversed linked list.
*/
public ListNode reverse(ListNode head) {
//prev表示前继节点
ListNode prev = null;
while (head != null) {
//temp记录下一个节点，head是当前节点
ListNode temp = head.next;
head.next = prev;
prev = head;
head = temp;
}
return prev;
}
}
