【Leetcode】重排链表、旋转链表、反转链表||

目录

💡重排链表

方法一：

方法二：

💡旋转链表

方法：

💡反转链表||

方法：

💡总结

---

💡重排链表

方法一：

将链表的每一个节点存在数组里，然后用下标访问的方式，交叉连接。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

typedef struct ListNode ListNode;
void reorderList(struct ListNode* head){
    if(head->next==NULL||head->next->next==NULL)
    return;
    ListNode* arr[50001];
    ListNode* cur=head;
    int n=0;
    while(cur)
    {
        arr[n]=cur;
        cur=cur->next;
        n++;
    }
    int i=0;
    int j=n-1;
    while(i<j)
    {
        arr[i]->next=arr[j];
        i++;
        
        arr[j]->next=arr[i];
        j--;
    }
        arr[i]->next=NULL;

}

方法二：

可以先用快慢指针的方法找到链表的中间节点，然后将中点后的链表翻转成一个新的链表，最后将这个新链表和原链表切割掉中间节点之后的链表合并成一个新的链表，合并方式是交叉合并。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

typedef struct ListNode ListNode;
ListNode* MiddleNode(ListNode* head)
{
    ListNode* fast=head;
    ListNode* slow=head;
    while(fast!=NULL&&fast->next!=NULL)
    {
        fast=fast->next->next;
        slow=slow->next;
    }
    return slow;
}
ListNode* ReverseList(ListNode* head)
{
    ListNode* phead=NULL;
    ListNode* cur=head;
    while(cur)
    {
        ListNode* tmp=cur->next;//注意先后顺序
        cur->next=phead;
        phead=cur;
        cur=tmp;
    }
    return phead;
}
void reorderList(struct ListNode* head){
    ListNode* mid=MiddleNode(head);
    ListNode* phead=ReverseList(mid->next);
    mid->next=NULL;
    ListNode* cur=head;
    while(phead)
    {
        ListNode* next=cur->next;
        cur->next=phead;
        ListNode* tmp= phead->next;
        phead->next=next;
        phead=tmp;
        cur=cur->next->next;
    }

}

💡旋转链表

方法：

要求每个节点向右移动k位置，其实就是将倒数k个结点接在头节点之前，倒数第k个结点成为新的头节点，但是这里需要对k进行处理，因为k可能大于链表长度，所以k=k%len，还有一个需要注意的就是当k==len时，是不需要进行任何操作的，直接返回头节点就可以了。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* rotateRight(struct ListNode* head, int k) {
    if(head==NULL||k==0)
    return head;
    ListNode* cur=head;
    ListNode* prev=head;
    ListNode* ret=head;
    int l=0;
    while(ret)
    {
        ret=ret->next;
        l++;
    }
    k=k%l;
    if(k==0)
    return head;
    while(k--)
    {
        cur=cur->next;
    }
    while(cur->next)
    {
        cur=cur->next;
        prev=prev->next;
    }

    ListNode*  Next=prev->next;
    cur->next=head;
    prev->next=NULL;
    return Next;
}

💡反转链表||

方法：

我的方法就是将区间[left,right]之间的结点翻转，然后与原来区间前后的结点重新连接起来。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head,struct ListNode* tail)
{
    ListNode*phead=NULL;//新的头
    ListNode*cur=head;
    while(cur!=tail)//遍历原链表
    {
        ListNode*next=cur->next;//保存下一个节点的地址，避免丢失
        cur->next=phead;
        phead=cur;//更新头节点
        cur=next;//继续遍历
    }
    return phead;
}
struct ListNode* reverseBetween(struct ListNode* head, int left, int right) {
    ListNode* cur1=head;
    ListNode* cur2=head;
    int cnt=1;
    while(cnt<left-1)
    {
        cur1=cur1->next;
        cur2=cur2->next;
        cnt++;
    }
    while(cnt<=right)
    {
        cur2=cur2->next;
        cnt++;
    }
    ListNode* tail=NULL;               
    if(cur2!=NULL)
        tail=cur2;
    if(left==1)
    head=reverseList(cur1,cur2);
    else
    cur1->next=reverseList(cur1->next,cur2);
    while(cur1->next)
    {
        cur1=cur1->next;
    }
    cur1->next=tail;

    return head;
}

💡总结

链表相关的题目还是要注意细节，结点之间的切割与连接要特别仔细，不然任意造成空结点，或者成环导致死循环。