链表插入与逆置

不带头结点的链表：

head（头指针）-->a1|next-->a2|next-->a3|next-->...-->an|NULL
第一个链表元素称为首结点，最后一个链表元素称为尾结点 

带头结点的链表

head（头指针）-->a|next（头结点）-->a1|next-->a2|next-->a3|next-->...-->an|NULL 
第一个链表元素称为首结点，最后一个链表元素称为尾结点 

插入链表元素（不带头结点链表）

LinkNode* head = NULL;  //链表建立
//若用void InsertLink(LinkNode** head, int pos, int x)则传入&head，且要注意head的使用
void InsertLink(LinkNode* &head, int pos, int x)  //pos==0----len-1 
{
    if (head == NULL)
    { 
        head = new LinkNode;
        head->data = x;
        head->next = NULL;
        return;
    }
    if (pos == 0)
    {
        LinkNode *now = new LinkNode;
        now->data = x;
        now->next = head;
        head = now;
        return;
    }

    LinkNode *pre = head;
    LinkNode *temp = NULL;
    LinkNode *now = new LinkNode;
    for (int i=1; i<pos; i++)
    {
        pre = pre->next; 
    }
//    while (pos > 0)
//    {
//        pre = pre->next; 
//        --pos;
//    }
    temp = pre->next;
    now->data = x;
    now->next = temp;
    pre->next = now;

    return;
} 

插入链表元素（带头结点）

LinkNode* head = CreateLink();  //链表建立
LinkNode* CreateLink(void)
{
    LinkNode *head = new LinkNode;
    head->next = NULL;
    return head;
}
//void InsertLink(LinkNode* &head, int pos, int x)亦可
void InsertLink(LinkNode* head, int pos, int x)  //pos==0----len-1
{
    LinkNode *pre = head;
    LinkNode *temp = NULL;
    for (int i=0; i<pos; i++)
    {
        pre = pre->next; 
    }
//    while (pos > 0)
//    {
//        pre = pre->next; 
//        --pos;
//    }
    LinkNode *cur = new LinkNode;
    temp = pre->next;
    cur->data = x;
    cur->next = temp;
    pre->next = cur;

    return;
} 

链表原地逆置（不带头结点）

//若用void ReverseList(LinkNode** head)则传入&head，且要注意head的使用
void ReverseList(LinkNode* &head)
{
    //申请节点，pre和 cur，pre指向null
    LinkNode* pre = NULL;
    LinkNode* cur = head;
    LinkNode* temp = NULL;
    while(cur != NULL) 
    {
        //记录当前节点的下一个节点
        temp = cur->next;
        //然后将当前节点指向pre
        cur->next = pre;

        //pre和cur节点都前进一位
        pre = cur;
        cur = temp;
    }
    head = pre;  //注意头指针已经修改
    return;
}

//递归版本逆置
ListNode* ReverseList(LinkNode* head)
{
    if (!head || !head->next)
    {
        return head;
    }

    auto tail = ReverseList(head->next);
    head->next->next = head;
    head->next = NULL;

    retur tail;
}

链表原地逆置（带头结点）

void ReverseLink(LinkNode* head)  //void ReverseList(LinkNode* &head)亦可
{
    //申请节点，pre和 cur，pre指向null
    LinkNode* pre = NULL;
    LinkNode* cur = head->next;
    LinkNode* tmp = NULL;
    while(cur != NULL) 
    {
        //记录当前节点的下一个节点
        tmp = cur->next;
        //然后将当前节点指向pre
        cur->next = pre;

        //pre和cur节点都前进一位
        pre = cur;
        cur = tmp;
    }
    head->next = pre;
    return;
}

链表原地逆置（带头结点）头插法自己写的

void ReverseList(LinkNode* head)  //void ReverseList(LinkNode* &head)亦可
{
    LinkNode* cur = head->next->next;  //跳过第一个元素，防止成环 
    LinkNode* temp = NULL;
    head->next->next = NULL;  //将第一个元素指向置为NULL 
    while (cur != NULL)
    {
        temp = cur->next;
        cur->next = head->next;
        head->next = cur;
        cur = temp;
    }
    return;    
} 

链表一定范围逆置

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* a = dummy;

        for (int i = 0; i < left - 1; ++i)
        {
            a = a->next;
        }

        auto b = a->next, c = b->next;
        for (int i = 0; i < right - left; ++i)
        {
            ListNode* temp = c->next;
            c->next = b;
            b = c, c = temp;
        }

        a->next->next = c;
        a->next = b;

        return dummy->next;
    }
};