单向链表的几道题

单向链表的几道题

 

---------------------------------------------------------------------------
1. 转置单向链表 (也就是反序，注意链表的边界条件并考虑空链表)。

#include

struct listtype
{
    int data;
    struct listtype * next;
};

typedef struct listtype * list;

/* Reverse the singly linked list *psll. */
void reverse_singly_linked_list(list * psll)
{
    list h = NULL;
    list p = *psll;

    if (!psll || !*psll)
    {
        return;
    }

    while (p)
    {
        list tmp = p;
        p = p->next;
        tmp->next = h;
        h = tmp;
    }

    *psll = h;
}

---------------------------------------------------------------------------

2. 在链表里如何发现循环链接？

#include

struct listtype
{
    int data;
    struct listtype * next;
};

typedef struct listtype * list;

/* Check that whether there is loop in the singly linked list sll or not. */
int find_circle(list sll)
{
    list fast = sll;
    list slow = sll;

    if (NULL == fast)
    {
        return -1;
    }

    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;

        if (fast == slow)
        {
            return 1;
        }
    }

    return 0;
}


参考：


---------------------------------------------------------------------------

3. 找到单向链表中间那个元素，如果有两个则取前面一个。

#include

struct listtype
{
    int data;
    struct listtype * next;
};

typedef struct listtype * list;

/* Find the middle element of the singly linked list sll. */
list find_middle(list sll)
{
    list slow = sll;
    list fast = sll;

    if (NULL == fast)
    {
        return NULL;
    }

    while (1)
    {
        if (NULL == fast->next || NULL == fast->next->next)
        {
            return slow;
        }

        slow = slow->next;
        fast = fast->next->next;

        /* Prevent that there is a loop in the linked list. */
        if (fast == slow)
        {
            return NULL;
        }
    }
}

---------------------------------------------------------------------------

4. 删除单链表的倒数第 m 个元素。
    给定一个单向链表 (长度未知)，请设计一个既节省时间又节省空间的算法来找出该链表中的倒数第 m 个元素。实现这个算法，并为可能出现的特例情况安排好处理措施。

#include

struct listtype
{
    int data;
    struct listtype * next;
};

typedef struct listtype * list;

/* Find the mth element of the singly linked list sll from the end. */
list find_the_mth_element_from_end(list sll, int m)
{
    list fast = sll; /* Used for loop detecting. */
    list ahead = sll;
    list after = sll;

    if (NULL == ahead || m <= 0)
    {
        return NULL;
    }

    while (m--)
    {
        if (NULL == ahead)
        {
            return NULL;
        }
        ahead = ahead->next;

        if (fast && fast->next)
        {
            fast = fast->next->next;
            if (fast == ahead)
            {
                return NULL;
            }
        }
    }

    while (1)
    {
        if (NULL == ahead)
        {
            return after;
        }
        ahead = ahead->next;
        after = after->next;

        if (fast && fast->next)
        {
            fast = fast->next->next;
            if (fast == ahead)
            {
                return NULL;
            }
        }
    }
}

---------------------------------------------------------------------------

5. 给定一个单向链表的头指针，要求找出该链表循环部分的第一个节点。如果该链表不是循环链表，则返回空指针。例如给定下面的链表：
    0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> (3) 循环
就应该返回结点 3 的指针。请优化时间和空间。

解法一：
一次遍历，把地址存入 hash 表就行了，第一次出现重复的地址就是需要的解。
时间复杂度 O(n)，空间复杂度 O(n)。

解法二：
把链表当做有向图，进行深度优先遍历，第一个回退边指向的节点即是需要的解。
时间复杂度 O(n)，空间复杂度 O(n)。

解法三：
首先根据链表创建一个逆序的链表。如下：
原始：1->2->3->4->5->6->7->8->(3)
逆序：1->2->3->8->7->6->5->4->(3)
然后分别从两个链表头指针开始，找到 next 指针不一样的那个节点就是最终目标了。
时间复杂度 O(n)，空间复杂度 O(n)。

解法四：
用两个步长分别为 1 和 2 的指针前进，第一次相遇之后再前进，第二次相遇时停止。记下从第一次相遇到第二次相遇，步长为 1 的指针走过的步数 S，则 S 为环的长度。然后用两个指针，一个在链头，一个走到链头后第 S 个位置上，同时以步长为 1 前进，判断两个指针是否相等，如果是就是环的起始位置了。
时间复杂度 O(n)，空间复杂度 O(1)。

解法五：(跟解法四的思想差不多，优于解法四，因为常数因子小)
用两个步长分别为 1 和 2 的指针前进，第一次相遇之后，令其中一个指针指向链表头。然后，令两个指针步长都为 1，同时前进，相遇时停止。该节点就是环的起始位置。
时间复杂度 O(n)，空间复杂度 O(1)。

下面给出解法五的 C 实现。

#include

struct listtype
{
    int data;
    struct listtype * next;
};

typedef struct listtype * list;

/*
 * Find the head node of the loop in the singly linked list sll.
 * If there is not a loop in sll, NULL is return.
 */
list find_head_of_loop(list sll)
{
    list slow = sll;
    list fast = sll;

    if (NULL == fast)
    {
        return NULL;
    }

    while (1)
    {
        if (NULL == fast->next || NULL == fast->next->next)
        {
            return NULL;
        }

        slow = slow->next;
        fast = fast->next->next;

        if (fast == slow)
        {
            slow = sll;
            break;
        }
    }

    while (1)
    {
        slow = slow->next;
        fast = fast->next;

        if (fast == slow)
        {
            return fast;
        }
    }
}


参考：


---------------------------------------------------------------------------

6. 给定一个单向链表的结点，要求在常数时间里删除该结点。

    常数时间删除结点肯定不行，不过可以用假删除，就是把要删除节点的值用要删除节点的下一个节点值覆盖，然后删除下一个节点 (要求该节点的下一个节点不能是空) ：
    p->data = p->next->data;
    temp = p->next;
    p->next = temp->next;
    free(temp);

 

   这一题目并非有误，我已找到解决的办法。如果解题方法不对还望大家积极讨论并找出解题方法。如果某人有更好的方法，也请拿来供大家共享，在此先谢过！

   初看这题目要求最为醒目的地方是时间复杂度为O(1)，这也是本题的难解之处，值得为之找到解决方法之处。时间复杂度要求为O(1)时出现的一系列情形：

　　首先是不能遍历链表，如果遍历链表时间复杂度就为O(n)了

　　不能遍历链表也就决定了不能找到被删除节点p的前一个节点的指针（用pre表示）

　　不能找pre节点，也就无法改变pre节点的next域

　　pre节点的next域无法改变也就决定了最终不能删除当前节点。

既然不能删除当前节点那只能是删除其它节点来代替了。这里有两种方法：

　　一是只删除head指向的节点来代替。

　　二是删除p节点的下一个节点来代替（这是小兵提到的假删除）。

以上两种删除方式通过删除节点和保留节点值的互换，时间复杂度是可以符合O(1)的。节点值的互换是怎样删除，这里用第一种删除方法解释一下：

假设链表的类型是List，先声明一个tmp，delete_onde指针变量并用它们进行如下操作

       List *tmp;

    List *delete_node;

             

              delete_node = head;// delete_node指向真正被删除的节点

        head = head->next;// head指向下一个节点

 

        // 下面操作是p所指向的节点和delete_node指向的节点值的互换

        // 即原来的头节点（delete_node）的值移到了原来p所指向的节点，原来p

        // 指向的节点值移到了原来的头节点，删除原来头节点也就是达到了删除目的。

        *tmp = *p;

        *p = *delete_node;

        p->next = tmp->next;

        *delete_node = *tmp;

        delete_node->next = NULL;

以上的代码操作只是方法一主要逻辑的解释，并没有作严格的检查判断。下面给出方法二的具体代码，正如小兵提到的情况一样：方法二删除的如果是最后一个节点会有问题。但是这并不是没有解决办法，我在处理代码时，如果遇到的是删除最后一个节点就用删除head所指向的节点来代替删除，这样这个问题就解决了。

主体代码就是22行的函数list_delete_node。

 

 

 1   #include

 2   #include

 3   #include

 4  

 5   typedef struct _List List;

 6  

 7   struct _List

 8   {

 9       List *next;

 10       void *private;

 11   };

 12  

 13   #define SWAP_NOTE_VALUE(node1, node2) \

 14            do{ \

 15                List tmp; \

 16                          \

 17                tmp = *(node2); \

 18                *(node2) = *(node1); \

 19                *(node1) = tmp; \

 20              }while(0)

 21  

 22   List *list_delete_node(List **head, List **del_node)

 23   {

 24       // "next" is a pointer that will be really point to the delete node.

 25       List *next;

 26  

 27       if((NULL == head) || (NULL == del_node))

 28           return NULL;

 29       if((NULL == *head) || (NULL == *del_node))

 30           return NULL;

 31  

 32       // Call list_delete_node(&head, &head);

 33       // Perhaps we consider this to be an error will be better!!!

 34       if(head == del_node)

 35       {

 36           next = *del_node;

 37           *head = (*head)->next;

 38           next->next = NULL;

 39           return next;

 40       }

 41  

 42       if(*head == *del_node) //if delete first node

 43       {

 44           *head = (*head)->next;

 45            (*del_node)->next = NULL;

 46            return *del_node;

 47       }

 48       else if(NULL == (*del_node)->next)

 49       {

 50         // If delete last node, use the head node for replacing delete

 51           next = *head;

 52           *head = (*head)->next;

 53           next->next = NULL;

 54  

 55           SWAP_NOTE_VALUE(*del_node, next);

 56           (*del_node)->next = NULL;

 57  

 58           *del_node = next;

 59           return *del_node;

 60       }

 61       else

 62       {

 63           next = (*del_node)->next;

 64           SWAP_NOTE_VALUE(*del_node, next);

 65  

 66           *del_node = next;

 67           (*del_node)->next = NULL;

 68           return *del_node;

 69       }

 70   }

 71  

 72   typedef void (*ListNodeVisitFunc)(List *node, void *user_data);

 73  

 74   void list_foreach(List *head, ListNodeVisitFunc node_visit_func, void *user_data)

 75   {

 76       List *node;

 77       List *next;

 78  

 79       node = head;

 80       while(node)

 81       {

 82           next = node->next;

 83           // if node_visit_func is free function. "node->next" will be error

 84           // after node_visit_func. So use the "next" variable here.

 85           node_visit_func(node, user_data);

 86           node = next;

 87       }

 88   }

 89  

 90   void list_node_free(List *node, void *user_data)

 91   {

 92       if(node->private)

 93           ;//free the private data

 94       free(node);

 95  }

 96  

 97   void init_list(List **head)

 98   {

 99       int i;

100  

101   #define TEST_LIST_LEN 10

102       for(i=0; i

103       {

104           List *node = malloc(sizeof(List));

105           node->private = (void *)i;

106           node->next = *head;

107           *head = node;

108       }

109   }

110  

111   void list_print(List *head)

112   {

113       List *node;

114  

115       for(node = head; node; node=node->next)

116           printf("the node is %d\n", node->private);

117       printf("\n");

118   }

119  

120   void test_list(List **list_head)

121   {

122       List *del_node;

123       List *return_node;

124       List *head;

125  

126       head = *list_head;

127  

128       list_print(head);

129       del_node = head;

130       return_node = list_delete_node(&head, &del_node); // test delete first node

131       assert(return_node == del_node);

132       printf("the deleted node is %d\n", del_node->private);

133       list_node_free(del_node, NULL);

134       return_node = del_node = NULL;

135       list_print(head);

136  

137       // get the last node to test delete last node

138       for(del_node=head; del_node->next; del_node=del_node->next)

139           ;//no op

140       return_node = list_delete_node(&head, &del_node);

141       assert(return_node == del_node);

142       printf("the deleted node is %d\n", del_node->private);

143       list_node_free(del_node, NULL);

144       return_node = del_node = NULL;

145       list_print(head);

146  

147       int i;

148       del_node = head;

149   #define MIDDLE_NOTE_FOR_TEST_DELETE 3

150       for(i=0; i

151       {

152           del_node = del_node->next;

153       }

154       return_node = list_delete_node(&head, &del_node);

155       assert(return_node == del_node);

156       printf("the deleted node is %d\n", del_node->private);

157       list_node_free(del_node, NULL);

158       return_node = del_node = NULL;

159       list_print(head);

160  

161       list_foreach(head, list_node_free, NULL);

162   }

163  

164   int main(void)

165   {

166       List *head = NULL;

167  

168       init_list(&head);

169       test_list(&head);

170  

171       return 0;

172   }