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

目录

💡重排链表

题目描述

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

 L0 → L1 → … → Ln-1 → Ln 
请将其重新排列后变为：

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

提示：

• 链表的长度范围为 [1, 5 * 104]
• 1 <= node.val <= 1000

方法一：

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

/**
 * 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;
    }

}

💡旋转链表

题目描述

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

提示：

• 链表中节点的数目在范围 [0, 500] 内
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 109

方法：

要求每个节点向右移动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;
}

💡反转链表||

题目描述

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

提示：

• 链表中节点数目为 n
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

方法：

我的方法就是将区间[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;
}

💡总结

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