YSMull
<-- Algorithm

Reverse Linked List

原题目地址

题目描述

反转一个单链表

分析

方法一

递归版的写法,参考stackoverflow上面的这个回答,很有启发。

方法二

维护两个指针,指针rHead指向反后的链表的头结点,lHead指向的是待反转连标点头结点。

左边链表 右边链表
null a->b->c->null
null<-a b->c->null
null<-a<-b c->null
null<-a<-b<-c null

代码

递归版本

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL) return NULL;
    if (head->next == NULL) return head;

    struct ListNode* second = head->next;
    head->next = NULL;
    struct ListNode* reversedList = reverseList(second);
    second->next = head;
    return reversedList;
}

haskell版

学习上面的思想后用haskell实现了一个反转列表函数,虽然效率比较低

reverse1 [] = []
reverse1 (x:[]) = [x]
reverse1 (x:xs) = reverse1 xs ++ [xs]

实际上haskell自己是这么实现的

reverse                 :: [a] -> [a]
#ifdef USE_REPORT_PRELUDE
reverse                 =  foldl (flip (:)) []
#else
reverse l =  rev l []
  where
    rev []     a = a
    rev (x:xs) a = rev xs (x:a)
#endif

两个指针版本

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *lHead = NULL;
    struct ListNode *rHead = head;

    while (rHead != NULL) {
        struct ListNode *ptr = rHead->next;
        rHead->next = lHead;
        lHead = rHead;
        rHead = ptr;
    }
    return lHead;
}