leetCode-0206_反转链表

Posted on | In |

题目描述

英文题目

  • Reverse a singly linked list.

    Example:

    1
    2
    Input: 1->2->3->4->5->NULL
    Output: 5->4->3->2->1->NULL
中文题目

  • 反转一个单链表。

    示例:

    1
    2
    输入: 1->2->3->4->5->NULL
    输出: 5->4->3->2->1->NULL

解决方法

方法一
  • 描述

原链表之前建立一个dummy node，因为首节点会变，然后从head开始，将之后的一个节点移到dummy node之后，重复此操作知道head成为末节点为止

  • 源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 反转链表 1->2-3->4
 
 @param head 不带头结点
 @return 反转后的链表 4->3->2->1
 */
struct ListNode *reverseList(struct ListNode *head)
{
    struct ListNode *cur = head;
    struct ListNode *prev = NULL;
    while (cur) {
        struct ListNode *temp = cur->next;
        cur->next = prev;
        prev = cur;
        cur = temp;
    }
    return prev;
}

/**
 反转链表测试
 */
void reverseList_test()
{
    SingleLinkListNode *head = single_link_list_create();
    single_link_list_insert_tail(head, 1);
    single_link_list_insert_tail(head, 2);
    single_link_list_insert_tail(head, 3);
    single_link_list_insert_tail(head, 4);
    
    printf("========反转链表测试========\n");
    single_link_list_dump_head(head);
    SingleLinkListNode *new = reverseList(head->next);
    single_link_list_dump(new);
}
方法二
  • 描述
  • 源码
1
2
3
4
5
6
7
8
9
10
11
12
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *root = NULL;
    struct ListNode *temp;
    
    while(head != NULL) {
        temp = head;
        head = head->next;
        temp->next = root;
        root = temp;
    }
    return root;
}

题目来源

Reverse Linked List

反转链表

线性表相关代码

数据结构-线性表