单链表反转，就是将链表中所有节点的指向改变方向，具体可以有四种方式。

迭代法

迭代法的思想很直接，每次改变一个节点的next指向，依次迭代到尾节点。

需要3个辅助节点：beg，mid，end

0U23460R-2.png

每次将mid指向beg，然后beg, mid, end整体向后移动一个单位，直到完成反转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ListNode* reverseList(ListNode* head) {
    if(head==NULL || head->next==NULL){
        return head;
    }
    ListNode *beg=NULL, *mid=head, *end=head->next;
    while(true){
        mid->next = beg;
        if(end==NULL){
            break;
        }
        beg = mid;
        mid = end;
        end = end->next;
    }
	return mid;
}

递归法

递归法的思想跟迭代法正好相反，且不易理解。从尾链表开始依次向前遍历，过程中改变每个节点的指向。

先给出代码，再做解释：

1
2
3
4
5
6
7
8
9
10
ListNode* reverseList(ListNode* head){
	if(head == NULL || head->next == NULL){
		return head;
	}
    ListNode *new_node = reverseList(head->next);
    head->next->next = head;
    head->next = NULL; 
    // 将新的头指针返回上层
    return new_node;
}

每次执行到new_node处时，都会深入链表一步，直到head->next==NULL时才不继续深入，此时返回的是链表反转之后的新头节点，并且该节点作为每步递归的返回值，一直在不断地向上层递归返回。

在过程中的操作可以用下面的简图来表示，1，2步分别代表着 head->next->next=head 以及 head->next=NULL 。

0U23413F-8.gif

再一次返回上层时，new_head仍然是4号节点，但是把3的next指向到2。

0U234D49-9.gif

依次向上层返回，过程中不断修改节点指向，从而完成链表反转。

头插法

头插法的思路也比较简单，设置一个哑节点，然后迭代地将链表中的节点插入到哑节点后，最后返回哑节点的next节点。

构建哑节点：

0U2342546-11.gif

将1节点插入到哑节点后：

0U2342R3-12.gif

这样也很容易写出代码：

1
2
3
4
5
6
7
8
9
10
11
ListNode* reverseList(ListNode* head){
    ListNode dummy(0);
    ListNode *curr=head, *nxt;
    while(curr){
        nxt = curr->next;
        curr->next = dummy.next;
        dummy.next = curr;
        curr = nxt;
    }
    return dummy.next;
}

原地置换法

所谓原地，就是直接对原链表进行修改。在过程中需要借助两个指针 beg 和 end。

过程可以参考简图：

0U2341592-16.gif

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ListNode* reverseList(ListNode* head){
    if(head == NULL || head->next == NULL){
        return head;
    }
    ListNode *beg, *end;
    beg = head;
    while(beg->next!=NULL){
        end = beg->next;
        beg->next = end->next;
        end->next = head;
        head = end;
    }
    return head;
}

以上四种方法建议熟记！！