链表

删除重复元素

一个已排序的链表的头 head ，删除原始链表中所有重复数字（只保留一个）的节点，只留下不同的数字。返回 已排序的链表 。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* deleteDuplicates(struct ListNode* head) {
    if(head==NULL||head->next==NULL)
        return head;
    
    struct ListNode *current=head->next, *pre=head, *tmp;

    while(current!=NULL){
        if(current->val==pre->val){
            tmp=current;
            current=current->next;
            pre->next=current;
            free(tmp);
        }else{
            pre=current;
            current=current->next;
        }
    }
    return head;
}

旋转链表

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

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

提示：

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

思路

我的思路

首先遍历链表，求出链表长度n，并找出尾节点tail
考虑到k的取值很可能超过所给链表的长度，所以需要对k进行处理，令k = k % n更新k值。用指针p找到第（n-k）个节点
将链表的后k个节点和前 n - k个节点拼接起来，并让head指向新的头节点，新的尾节点即p节点的next指针指向null。

官方思路

首先考虑到k的取值很可能超过所给链表的长度，所以需要对k进行处理，假设链表长度为n，则令k = k % n，保证k值小于链表长度。

我们可以知道，新链表的顺序为：后面k（处理后）个节点——>前面n-k个节点。

要获取链表长度就需要遍历，然后我们可以先将给定的链表连接成环，最后在指定位置断开就形成了最终的链表。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* rotateRight(struct ListNode* head, int k) {
    if (!head || !head->next || k == 0) return head;

    // Step 1: 获取链表长度，并使链表形成环
    int len = 1;
    struct ListNode* p = head;
    while (p->next) {
        p = p->next;
        len++;
    }
    p->next = head; // 形成环形链表

    // Step 2: 若k大于链表长度，对k进行取模，避免多余旋转
    k %= len;
    if (k == 0) {
        p->next = NULL; // 恢复原状后返回，无需旋转
        return head;
    }

    // Step 3: 找到新链表的头节点位置（跳过最后k个节点）
    for (int i = 0; i < len - k; i++) {
        p = p->next;
    }

    // Step 4: 断开环，设置新头节点和原尾节点
    struct ListNode* new_head = p->next;
    p->next = NULL;

    return new_head;
}