206. Reverse Linked List(Linked List-Easy)

Jack_Cui

发布于 2018-01-08 16:06:11

4790

发布于 2018-01-08 16:06:11

文章被收录于专栏：Jack-Cui Jack-CuiJack-Cui

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

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017-03-08 ，如有侵权请联系 cloudcommunity@tencent.com 删除

python