反转单链表

方法一：逐个改变每一个结点指向下一个节点的指针.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    
    struct ListNode *next_node;
    struct ListNode *tmp_node;
    tmp_node=NULL;
    while(head)
    {
        next_node=head->next;
        head->next=tmp_node;
        tmp_node=head;
        head=next_node;
    }
    return tmp_node;
}

方法二：运用递归，对于head节点，head->next进行反转并返回，只要将head的插入到返回的链表的末尾

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


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

Contents