数据结构-链表旋转

---

链表旋转

链表旋转有指定一段旋转，也有整个链表旋转。我这边讲述下整个链表旋转，因为核心的思想都是一样的。

核心思想

构建三个指针head,pre,cur。
其中，head->next指向我们待旋转链表的头结点。pre指向头结点。cur指向第二个结点。
每一次的操作都是一样的，如下

tmp = head->next;
pre->next = cur->next;
head->next = cur;
cur->next = tmp;
cur = pre->next;

理解了上面的核心代码，链表旋转就完成一大半了，剩下要做的就是让链表循环起来及一些边界条件的判断，如下

typedef struct ListNode
{
    struct ListNode* next;
    int val;
    ListNode(int n) : val(n) , next(NULL) {}
};

ListNode* reserve(ListNode* root){

    if(!root || !root->next) return root;
    
    ListNode* head = new ListNode(-1);  //新建一个结点指向我们待旋转链表的头结点
    head->next = root;
    ListNode* pre = root;
    ListNode* cur = root->next;
    ListNode* tmp = NULL;

    while(cur)
    {
        tmp = head->next;
        pre->next = cur->next;
        head->next = cur;
        cur->next = tmp;
        cur = pre->next;    
    }

    tmp = head->next;   
    delete head;		//旋转完，释放新建的结点，防止内存泄露
    head = NULL;
    return tmp;
}

---

---

总结

关于链表的一些操作其实还是算简单的，只要搞清楚了链表结点之间的指向关系，一般都可以搞定~~

---