HackerRank上单链表的相关题目(https://www.hackerrank.com/domains/data-structures/linked-lists)

LinkedLists.cpp

// 打印链表中的元素
void Print(Node *head) {
    if (head == NULL) {
        return;
    } 
    Node *ptr = head->next;
    while(ptr != NULL) {
        cout << ptr->data << endl;
        ptr = ptr->next;
    }
}

// 在链表尾部插入元素
Node *Insert(Node *head, int data) {
    Node *newCell = (Node *)malloc(sizeof(Node));
    newCell->data = data;
    newCell->next = NULL;
    if (head == NULL) {
        return newCell;
    } else {
        Node *tail = head;
        while(tail->next != NULL) {
            tail = tail->next;
        }
        tail->next = newCell;
        return head;
    }
}

// 在链表头部插入元素
Node *Insert(Node *head,int data) {
    Node *newCell = (Node *)malloc(sizeof(Node));
    newCell->data = data;
    if (head == NULL) {
        newCell->next = NULL;
        return newCell;
    } else {
        newCell->next = head;
        return newCell;
    }
}

// 在距离链表头部N的位置插入元素
Node * InsertNth(Node *head, int data, int position) {
    Node *newCell = (Node *)malloc(sizeof(Node));
    newCell->data = data;
    if (head == NULL) {
        newCell->next = NULL;
        return newCell;
    } else {
        if (position == 0) {
            newCell->next = head;
            return newCell;
        } else {
            int i = 1;
            Node *ptr = head;
            while(ptr != NULL && i != position) {
                i++;
                ptr = ptr->next;
            }
            newCell->next = ptr->next;
            ptr->next = newCell;
            return head;
        }
    }
}

// 删除距离链表头部N的位置的元素
Node *Delete(Node *head, int position) {
    if (head == NULL) {
        return NULL;
    } else {
        Node *ptrToNode;
        if (position == 0) {
            ptrToNode = head->next;
            free(head);
            return ptrToNode;
        } else {
            int i = 1;
            ptrToNode = head;
            while(ptrToNode != NULL && i != position) {
                i++;
                ptrToNode = ptrToNode->next;
            }
            Node *temp = ptrToNode->next;
            ptrToNode->next = temp->next;
            free(temp);
            return head;
        }
    }
}

// 逆序打印链表中的元素
void ReversePrint(Node *head) {
    if(head) {
        ReversePrint(head->next);
        cout << head->data << endl;
    } else {
        return;
    }
}

// 逆序单链表
Node* Reverse(Node *head) {
    if (head == NULL) {
        return NULL;
    } else {
        Node *reverseHead = NULL;
        Node *cur = head;
        Node *pre = NULL;
        Node *next = NULL;
        while(cur != NULL) {
            next = cur->next;
            if (next == NULL) {
                reverseHead = cur;
            }
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return reverseHead;
    }
}

// 比较两个链表是否相同
int CompareLists(Node *headA, Node* headB) {
    if(headA == NULL && headB == NULL) {
        return 0;
    } else if ((!headA && headB) || (headA && !headB)){
        return 0;
    } else {
            Node *ptrToA = headA, *ptrToB = headB;
            while(ptrToA && ptrToB && (ptrToA->data == ptrToB->data)) {
                ptrToA = ptrToA->next;
                ptrToB = ptrToB->next;
            }
            if(ptrToA == NULL && ptrToB == NULL) {
                return 1;
            } else {
                return 0;
            }
    }
}

// 合并两个有序链表
Node *MergeLists(Node *headA, Node *headB) {
    if (headA == NULL && headB == NULL) {
        return NULL;
    } else if (! headA && headB) {
        return headB;
    } else if (headA && !headB) {
        return headA;
    } else {
        Node *ptrToA = headA, *ptrToB = headB;
        Node *cur = (Node *)malloc(sizeof(Node));
        Node *head = cur;
        while(ptrToA && ptrToB) {
            while(ptrToA && ptrToB && (ptrToA->data < ptrToB->data)) {
                Node *newCell = (Node *)malloc(sizeof(Node));
                newCell->data = ptrToA->data;
                cur->next = newCell;
                cur = newCell;
                ptrToA = ptrToA->next;
            }
            while(ptrToA && ptrToB && (ptrToA->data > ptrToB->data)) {
                Node *newCell = (Node *)malloc(sizeof(Node));
                newCell->data = ptrToB->data;
                cur->next = newCell;
                cur = newCell;
                ptrToB = ptrToB->next;
            }
            while(ptrToA && ptrToB && (ptrToA->data == ptrToB->data)) {
                Node *newCell = (Node *)malloc(sizeof(Node));
                newCell->data = ptrToA->data;
                cur->next = newCell;
                cur = newCell;
                ptrToA = ptrToA->next;
                ptrToB = ptrToB->next;
            }
        }
        if(!ptrToA && ptrToB) {
            while(ptrToB) {
                Node *newCell = (Node *)malloc(sizeof(Node));
                newCell->data = ptrToB->data;
                cur->next = newCell;
                cur = newCell;
                ptrToB = ptrToB->next;
            }
            cur->next = NULL;
        } else if(ptrToA && !ptrToB) {
            while(ptrToA) {
                Node *newCell = (Node *)malloc(sizeof(Node));
                newCell->data = ptrToA->data;
                cur->next = newCell;
                cur = newCell;
                ptrToA = ptrToA->next;
            }
            cur->next = NULL;
        } else if (!ptrToA && !ptrToB ) {
            cur->next = NULL;
        }
        return head->next;
    }
}

// 获得距离链表尾部N位置处的元素
int GetNode(Node *head, int positionFromTail) {
    Node *p, *cur;
    p = cur = head;
    for(int i = 0; i <= positionFromTail;i++) {
        if (p != NULL) {
            p = p->next;
        }
    }
    while(p) {
        cur = cur->next;
        p = p->next;
    }
    return cur->data;
}

// 删除链表中的重复元素
Node *RemoveDuplicates(Node *head) {
    if(head == NULL) {
        return NULL;
    } else {
        Node *cur = head, *fol = cur->next;
        while(fol != NULL) {
            while(fol && (fol->data == cur->data)) {
                fol = fol->next;
            }
            cur->next = fol;
            if(fol) {
                cur = fol;
                fol = cur->next;
            }
        }
        return head;
    }
}

// 判断链表中是否有环
bool has_cycle(Node *head) {
    if(head == NULL) {
        return false;
    } else {
        Node *p = head, *q = head;
        while(p && q && q->next) {
            q = q->next->next;
            p = p->next;
            if(p == q) {
                return true;
            }
        }
        return false;
    }
}

// 查找链表的合并节点
int FindMergeNode(Node *headA, Node *headB) {
    Node *ptrToA = headA,*ptrToB = headB;
    int lenA,lenB;
    lenA = lenB = 0;
    while(ptrToA) {
        lenA++;
        ptrToA = ptrToA->next;
    }
    while(ptrToB) {
        lenB++;
        ptrToB = ptrToB->next;
    }
    ptrToA = headA,ptrToB = headB;
    if(lenA < lenB) {
        Node *temp = ptrToB;
        ptrToB = ptrToA;
        ptrToA = temp;
        int x = lenA;
        lenA = lenB;
        lenB = x;
    }
    for(int i = 0; i < lenA-lenB;i++) {
        ptrToA = ptrToA->next;
    }
    while(ptrToA && ptrToA != ptrToB) {
        ptrToA = ptrToA->next;
        ptrToB = ptrToB->next;
    }
    return ptrToA->data;

}

// 向一个有序双向循环链表中插入元素
Node *SortedInsert(Node *head, int data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    if(head == NULL) {
        newNode->next = NULL;
        newNode->prev = NULL;
        return newNode;
    } else {
        if(data < head->data) {
            newNode->next = head;
            head->prev = newNode;
            newNode->prev = NULL;
            return newNode;
        } else {
            Node *ptr = head,*cur;
            while(ptr && (data > ptr->data)) {
                cur = ptr;
                ptr = ptr->next;
            }
            if(! ptr) {
                cur->next = newNode;
                newNode->next = NULL;
                newNode->prev = cur;
                return head;
            } else {
                cur->next = newNode;
                newNode->next = ptr;
                newNode->prev = cur;
                ptr->prev = newNode;
            }
            return head;
        }
    }
}

// 逆序一个双向循环链表
Node * Reverse(Node *head) {
    if (head == NULL) {
        return NULL;
    } 
    Node *cur = head, *next = NULL,*reversedHead = NULL;
    while(cur) {
        next = cur->next;
        if (next == NULL) {
            reversedHead = cur;
        }
        cur->next = cur->prev;
        cur->prev = next;
        cur = next;
    }
    return reversedHead;
}