纯C手撕leetcode-基本数据结构-链表

技巧

1. 假头
2. 新链表
3. 双指针（正反向指针，快慢指针）
4. 递归

例子：
1.合并两个有序链表（假头，新链表）

2. 链表反转（假头/递归）

   
   image.png

//Definition for singly-linked list.
struct ListNode {
      int val;
      struct ListNode *next;
};
//递归实现
struct ListNode* reverseList(struct ListNode* head){
    if (head == NULL || head->next == NULL)
        return head;
    
    struct ListNode*cur,*next;
    cur= head;
    next=cur->next;
    struct ListNode* newH = reverseList(next);
    next->next= cur;
    cur->next = NULL;

    return newH;
}

3. K个一组反转（假头/递归/多指针）

   
   image.png

struct ListNode*reverse(struct ListNode* head) {
    struct ListNode* result = NULL;
    struct ListNode* p = head, *next=NULL;
    while(p) {
        next= p->next;
        p->next=result;
        result=p;
        p=next;
    }

    return result;
}

struct ListNode* reverseKGroup(struct ListNode* head, int k){
    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    struct ListNode* former;
    struct ListNode* start, *end,*p, *follow;
    int len;
    dummy->next = head;

    p=dummy;

    while(p) {
        len = k;
        //1.get former;
        former = p;

        //2.get start
        start = former->next;
        
        //3.check have k numbers
        while( p->next && len) {
            p=p->next;
            len--;
        }
            
        //4.不足k个，不处理
        if (len > 0)
            break;

        //5.get end;
        end = p;

        //6.get follow
        follow = p->next;
        //7. 处理[former, follow]
        end->next = NULL;
        former->next=NULL;
        reverse(start);
        former->next = end;
        start->next = follow;
        
        p = start;

    }

    return dummy->next;
}