链表例题

链表求逆序

Reverse a linked list from position m to n. Do it in-place and in one-pass. For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4, return 1->4->3->2->5->NULL.

class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
       int len = 0;
        ListNode *first = NULL,*last = NULL, *node1 = head;
        while(node1 != NULL){
            len ++;
            if(len == m-1){
                first = node1;
            }
            if(len == n+1){
                last = node1;
            }
            node1 = node1->next;
        }
        if(first == NULL){
            node1 = head;
        }else{
            node1 = first->next;
        }
        ListNode *head2 = last;
        ListNode *node2;
        
        while(node1 != last){
            node2 = node1->next;
            node1->next = head2;
            head2 = node1;
            node1 = node2;
        }
        if(first != NULL){
            first->next = head2;
            return head;
        }
        return head2;
    }
};

链表求交点

Write a program to find the node at which the intersection of two singly linked lists begins.

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int len1 = 0;
        int len2 = 0;
        ListNode *n1 = headA, *n2 = headB;
        while(n1 != NULL){
            len1++;
            n1 = n1->next;
        }
        while(n2 != NULL){
            len2++;
            n2 = n2->next;
        }
        if(len1 - len2 > 0){
            for(int i=0;i<len1 - len2;i++){
                headA = headA->next;
            }    
        }else{
            for(int i=0;i<len2 - len1;i++){
                headB = headB->next;
            }
        }
        while(headA!=NULL){
            if(headA == headB){
                return headA;
            }
            headA = headA->next;
            headB = headB->next;
        }
        return NULL;
    }
};

链表求环

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.Can you solve it without using extra space?

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == NULL || head->next == NULL || head->next->next == NULL){
            return NULL;
        }
        ListNode *slow = head->next;
        ListNode *fast = head->next->next;
        
        while(slow != fast){
            if(fast->next == NULL || fast->next->next == NULL){
                return NULL;
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        slow = head;
        while(slow != fast){
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};

链表划分

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.You should preserve the original relative order of the nodes in each of the two partitions.For example, Given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5.

class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        ListNode *less = new ListNode(0);
        ListNode *greater = new ListNode(0);
        ListNode *h1 = less, *h2 = greater; 
        while(head != NULL){
            if(head->val < x){
                less->next = head;
                less = less->next;
            }else{
                greater->next = head;
                greater = greater->next;
            }
            head = head->next;
        }
        greater->next = NULL;
        less->next = h2->next;
        ListNode *node = h1->next;
        delete h1;
        delete h2;
        return node;
    }
};

复杂链表的复制

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list.

struct RandomListNode{
    int label;
    RandomListNode *next, *random;
    RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
};

class Solution
{
  public:
    RandomListNode *copyRandomList(RandomListNode *head){
        vector<RandomListNode *> v;
        map<RandomListNode*,int> m;
        RandomListNode *node = head;
        int i = 0;
        while (node != NULL){
            v.push_back(new RandomListNode(node->label));
            m.insert(make_pair(node,i));
            i++;
            node = node->next;
        }
        v.push_back(NULL);
        node = head;
        i = 0;
        while(node != NULL){
            v[i]->next = v[i+1];
            if(node->random == NULL){
                v[i]->random = NULL;
            }else{
                int j = m[node->random];
                v[i]->random = v[j];
            }
            i++;
            node = node->next;
        }
        return v[0];
    }
};

K个排序链表的归并

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

class Solution {
public:
    ListNode *merge(ListNode *n1, ListNode *n2){
        ListNode *head = new ListNode(0);
        ListNode *node = head;
        while(n1 != NULL && n2 != NULL){
            if(n1->val < n2->val){
                node->next = n1;
                n1 = n1->next;
            }else{
                node->next = n2;
                n2 = n2->next;
            }
            node = node->next;
        }
        while(n1 != NULL){
            node->next = n1;
            n1 = n1->next;
            node = node->next;
        }
        while(n2 != NULL){
            node->next = n2;
            n2 = n2->next;
            node = node->next;
        }
        node = head->next;
        delete head;
        return node;
    }
    
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        while(lists.size()>1){
            ListNode *node = merge(lists[0],lists[1]);
            lists.push_back(node);
            lists.erase(lists.begin());
            lists.erase(lists.begin());
        }
        if(lists.size() == 0){
            return NULL;
        }
        return lists[0];
    }
};