206. Reverse Linked List(Linked List-Easy)

转载请注明作者和出处： http://blog.csdn.net/c406495762

Reverse a singly linked list.

Hint:

A linked list can be reversed either iteratively or recursively. Could you implement both?

题目：反转单链表，可以使用迭代或者递归的方法。

    迭代的方法，简单说下就是：当迭代到最深层，返回的时候cur的地址和new_head的地址是一致的。操作cur就相当于操作new_head。head->next = NULL 就是将已经返回后的值丢掉。

Language：C

iteratively ：

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

recursively：

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head) { struct ListNode* cur = (struct ListNode *)malloc(sizeof(struct ListNode)); struct ListNode* new_head = (struct ListNode *)malloc(sizeof(struct ListNode)); if(head == NULL || head->next == NULL){ return head; } //迭代到最深层，返回的时候cur的地址和new_head的地址是一致的。操作cur就相当于操作new_head。head->next = NULL 就是将已经返回后的值丢掉。 cur = head->next; new_head = reverseList(cur); head->next = NULL; cur->next = head; return new_head; }

Language : python

# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def reverseList(self, head): """ :type head: ListNode :rtype: ListNode """ pre = None while head: cur = head head = head.next cur.next = pre pre = cur return pre

LeetCode题目汇总： https://github.com/Jack-Cherish/LeetCode

Jack-Cui 认证博客专家 算法工程师 微信公众号搜索【JackCui-AI】，关注这个爱发技术干货的程序员。个人网站：https://cuijiahua.com