Niuke linked list solution record

Niuke network algorithm

Reverse a linked list

struct ListNode* ReverseList(struct ListNode* pHead ) {
    
	  if(!pHead) return pHead;
	  struct ListNode *p = NULL,*tmp;
	  while (pHead->next)
	  {
    
	    tmp = pHead->next;
	    pHead->next = p;
	    p = pHead;
	    pHead = tmp;
	  }
	  pHead->next = p;
	  return pHead;
}

Reverse the specified interval in the linked list

struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
    
	  if (!head) return NULL;
	  struct ListNode*p = NULL,*tmp=head,*q,*tail,*pre= NULL;
	  n-=m-1;
	  while(--m) {
    
	    pre = tmp;
	    tmp=tmp->next;
	  } 
	  tail=tmp;
	  while (n)
	  {
    
	    q = tmp->next;
	    tmp->next = p;
	    p = tmp;
	    tmp = q;
	      n--;
	  }
	  if(pre) {
    
	    pre->next = p;
	  } else {
    
	    head = p;
	  }
	  tail->next = tmp;
	  return head;
}

Every node in the linked list k Turn over in groups

//  Merge two linked lists 
struct ListNode* ReverseList(struct ListNode* pHead,struct ListNode* tail) {
    
    struct ListNode *p = tail->next,*tmp;
    while (pHead->next != tail->next ) {
    
        tmp = pHead->next;
        pHead->next = p;
        p = pHead;
        pHead = tmp;
    }
    pHead->next = p;
    return pHead;
}

struct ListNode* reverseKGroup(struct ListNode* head, int k ) {
    
    // write code here
    if(!head || k==1) return head;
    struct ListNode *p = malloc(sizeof(struct ListNode *));
    p->next = head;
    struct ListNode *tmp=p,*q=head,*tail;
    int count = 1;
    while (q->next){
    
        count ++;
        q = q->next;
        if (count == k) {
    
            tail = q->next;
            tmp->next=ReverseList(head,q);
            tmp = head;
            head = tail;
            q = tail;
            count = 1;
        }
    }
    return p->next;
}

Judge whether there are links in the list

The entry node of a link in a list The solution is the same , The first access to the marked node is the entry node

//  Method 1 ： The presence of a ring indicates that the previous element has been accessed , By marking 
//  Method 2 ： Speed pointer , When the speed pointers are equal, it means there is a ring 
bool hasCycle(struct ListNode* head ) {
    
    // write code here
    int max = 1e8;
    int t = max>>1; // val  With negative numbers 
    while (head)
    {
    
        if (head->val>t) return true;
        head->val += max;
        head=head->next;
    }
    return false;
}

Last in the list k Nodes

struct ListNode* FindKthToTail(struct ListNode* pHead, int k ) {
    
    //  Give Way fast  Than  slow  Move first k Nodes 
    if (!pHead) return NULL;
    struct ListNode* slow=pHead,*fast=pHead;
    while(fast&&k--) {
    
        fast=fast->next;
    }
    //  Whether it is longer than the length of the linked list itself 
    if(!fast&&k) return NULL;
    while (fast)
    {
    
        fast = fast->next;
        slow = slow->next;
    }
    return slow; 
}

Delete the last of the linked list n Nodes

struct ListNode* removeNthFromEnd(struct ListNode* pHead, int k ) {
    
    //  Give Way fast  Than  slow  Move first k Nodes 
    if (!pHead) return NULL;
    // p  Point to slow In front of 
    struct ListNode* slow=pHead,*fast=pHead,*p; 
    while(fast&&k--) {
    
        fast=fast->next;
    }
    //  Whether it is longer than the length of the linked list itself 
    if(!fast&&k) return NULL;
    while (fast)
    {
    
        fast = fast->next;
        p = slow;
        slow = slow->next;
    }
    if(!p) return pHead->next; //  The first node is deleted 
    p->next = slow->next;
    free(slow);
    return pHead;
}

The first common node of two linked lists

struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 ){
    
    int max = 1e7;
    int t = max>>1;
    while (pHead1) {
    
        pHead1->val += max;
        pHead1 = pHead1->next;
    }
    while (pHead2){
    
        if(pHead2->val>t) {
    
            //  Change back to the original value 
            struct ListNode *p = pHead2;
            while (p) {
    
                p->val -=max;
                p = p->next;
            }
            return pHead2;
        }
        pHead2 = pHead2->next;
    }
    return NULL;
}

Add the linked list ( Two )

void tail_insert(struct ListNode*p, int val) {
    
    struct ListNode *q = (struct ListNode *) malloc(sizeof(struct ListNode));
    q->val = val;
    q->next = NULL;
    p->next = q;
}

void inc(struct ListNode* head) {
    
    //  For a linked list +1
    int carry = 1;
    struct ListNode *p;
    while (head){
    
        head->val += carry;
        if (head->val > 9) {
    
            carry = 1;
            head->val = 0;
        } else {
    
            carry = 0;
            return;
        }
        p = head;
        head = head->next;
    }
    //  You need to create a new node 
    tail_insert(p,1);
}

struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
    
    //  First, reverse the two linked lists 
    struct ListNode *p1 = ReverseList(head1);
    struct ListNode *p2 = ReverseList(head2);
    struct ListNode *tmp1=p1, *tmp2=p2,*p;
    int carry = 0; //  carry 
    while (tmp1&&tmp2)
    {
    
        tmp1->val += tmp2->val+carry;
        if (tmp1->val > 9) {
    
            carry = 1;
            tmp1->val -= 10;
        } else {
    
            carry = 0;
        }
        tmp2->val = tmp1->val;
        p = tmp1;
        tmp1 = tmp1->next;
        tmp2 = tmp2->next;
    }
    if (tmp2) {
    
        // tmp2 > tmp1  The length of 
        inc(tmp2);
        return ReverseList(p2);
    }
    if (carry) {
    
        // tmp1 The length of >= tmp2 The length of , But it still needs to increase by itself 
        inc(tmp1);
    }
    return ReverseList(p1);
}

Determine whether a linked list is palindrome structure

int a[100001] = {
    0};

bool isPail(struct ListNode* head) {
    
    int len = 0;
    while(head) {
    
        a[len++] = head->val;
        head = head->next;
    }
    int j = len>>1;
    for (int i=0;i<j;++i) {
    
        if (a[i]!=a[len-1-i]) return false;
    }
    return true;
}

Parity rearrangement of linked list

struct ListNode* oddEvenList(struct ListNode* head ) {
    
    struct ListNode *p1,*p2,*tmp1,*tmp2;
    p1 = malloc(sizeof(struct ListNode));
    p2 = malloc(sizeof(struct ListNode));
    tmp1 = p1;
    tmp2 = p2;
    int len = 0;
    while(head) {
    
        len++;
        if (len&1) {
    
            tmp1->next = head;
            tmp1 = head;
        } else {
    
            tmp2->next = head;
            tmp2 = head;
        }
        head = head->next;
    }
    tmp2->next = NULL;
    tmp1->next = p2->next;
    return p1->next;
}

Delete duplicate elements in the ordered linked list -I

struct ListNode* deleteDuplicates(struct ListNode* head) {
    
    if (!head) return NULL;
    struct ListNode* p = head,*tmp=head->next;
    int val = head->val;
    while(tmp) {
    
        if (tmp->val != val) {
    
        	  //  If not repeated p Need to point to the next 
            val = tmp->val;
            p = p->next;
        } else {
    
            p->next = tmp->next;
        }
        tmp = tmp->next;
    }
    return head;
}

Delete duplicate elements in the ordered linked list -II

struct ListNode* deleteDuplicates(struct ListNode* head ) {
    
    if (!head) return NULL;
    struct ListNode *p = malloc(sizeof(struct ListNode));
    p->next = NULL;
    struct ListNode *q = head,*tmp=head->next,*tmp_p=p;
    int val = head->val;
    int count = 1; //  Count 
    while(tmp) {
    
        if (tmp->val != val) {
    
            val = tmp->val;
            if (count == 1) {
    
                tmp_p->next = q;
                tmp_p = q;
            } else {
    
                free(q);
            }
            count = 1;
        } else {
    
            free(q);
            count ++;
        }
        q = tmp;
        tmp = tmp->next;
    }
    if (count==1) {
    
        //  The last one is not a repeating element 
        tmp_p->next = q;
    } else {
    
        tmp_p->next = NULL;
        free(q);
    }
    tmp_p = p->next;
    free(p);
    return tmp_p;
}

The sort of single linked list

//  Use quick sort 
struct ListNode* sortInList(struct ListNode* head) {
    
    // write code here
    if (!head) return NULL;
    // print_list(head);
    struct ListNode *low = malloc(sizeof(struct ListNode));
    struct ListNode *high = malloc(sizeof(struct ListNode));
    int val = head->val;
    struct ListNode *q=head->next,*p1=low,*p2=high;
    while (q)
    {
    
        if (q->val<val) {
    
            p1->next = q;
            p1 = q;
        } else {
    
            p2->next = q;
            p2 = q;
        }
        q = q->next;
    }
    p1->next=p2->next = NULL;
    low->next = sortInList(low->next);
    high->next = sortInList(high->next);
    p1 = low;
    while (p1->next) {
    
        p1 = p1->next;
    }
    p1->next = head;
    head->next = high->next;
    head = low->next;
    free(low);
    free(high);
    return head; 
}