程序员代码面试指南 2.5：反转部分单向链表

1、思路

• 需要得到四个节点的位置：反转链表的前一个节点before，反转链表的起始节点start，反转链表的末尾结点end以及反转链表末尾结点的后一个节点after；

• 将start与end之间的链表进行反转，反转后end变成了表头，start变成了表尾；

• 最后再将这四个节点连接起来即可。

2、代码

list_node * reverse_list(list_node * head, int L, int R)
{
    if (head == nullptr || head->next == nullptr) return head;

    auto dummy = new list_node;             //定义虚拟头结点，因为反转链表可能从第一个元素开始
    dummy->next = head;

    auto before = dummy, end = head;        //注意before与end的初始位置
    while ( -- L  && before->next != nullptr) before = before->next;
    while ( -- R && end->next != nullptr) end = end->next;

    auto start = before->next, after = end->next;

    auto pre = start, cur = start->next;    //反转链表的模板
    while (cur != after)
    {
        auto ne = cur->next;
        cur->next = pre;
        pre = cur, cur = ne;
    }

    before->next = end;     //连接表头
    start->next = after;    //连接表尾

    return dummy->next;
}