单向链表相关算法题(C++)

根据上一篇链表创造个管理对链表的理解（https://www.jianshu.com/p/d1fdc35e7546），从而延伸出的相关算法：

1.打印两个有序链表的公共部分

/**
     * 打印两个有序链表的公共部分
     * @param head1
     * @param head2
     *
     * 思路：
     * 1：判断head1的值是否小于head2的值，则head1往下移动，否则head2往下移动。
     * 2：如果head1的值和head2的值相等，则打印这个值，然后head1与和head2都往下移动。
     * 3：如果其中一个头结点指针为null，则结束打印。
     *
     */
    void printCommonPart(IntSLLNode* head1, IntSLLNode* head2) {

        if (head1 == 0 && head2 == 0) {
            return;
        }

        while (head1 != 0 && head2 != 0) {
            if (head1->info < head2->info) {
                head1 = head1->next;
            } else if (head2->info < head1->info) {
                head2 = head2->next;
            } else {
                std::cout<<"公共部分值为："<<head1->info<<std::endl;
                head1 = head1->next;
                head2 = head2->next;
            }
        }
    }

2、删除单链表中倒数第k个节点

/**
     * 删除单链表中倒数第k个节点
     * @param head
     * @param lastKth
     * @return
     *
     * 思路：
     * 1：k>0说明，k值超出链表范围
     * 2：k == 0说明，刚好是链表的头结点。
     * 3：k < 0说明，k - n刚好得到要删除节点的前一个节点的位置。
     *
     * 注意：因为得到负数lastKth是要删除节点的前一个，所以要先++，然后在移动指针，要不节点位置会计算错误。
     */
    IntSLLNode* removeLastKthNode(IntSLLNode* head, int lastKth) {
        if (head == 0 && lastKth < 1) {
            return head;
        }
        IntSLLNode *cur = head;
        while (cur != 0) {
            lastKth--;
            cur = cur->next;
        }

        if (lastKth == 0) {
            head = head->next;
        }

        if (lastKth < 0) {
            cur = head;
            while (++lastKth != 0) {
                cur = cur->next;
            }
            cur->next= cur->next->next;
        }
        return head;
    }

3、删除链表的中间节点

/**
     * 删除链表的中间节点
     * @param head
     * @return
     *
     * 思路：
     * 规律：链表长度每增加2，要删除的节点才往后移动一个节点。
     */
    IntSLLNode* removeMidNode(IntSLLNode* head) {
        if (head == 0 || head->next == 0) {
            return head;
        }

        if (head->next->next == 0) {
            return head->next;
        }

        IntSLLNode* pre;
        IntSLLNode* cur = head->next->next;
        while (cur->next != 0 && cur->next->next != 0) {
            pre = pre->next;
            cur = cur->next->next;
        }
        pre->next = pre->next->next;

        return head;
    }

4、单向链表反转

/**
     * 单向链表反转
     * @param head
     * @return
     * 思路：
     * 定义两个节点指针，一个指针的作用是用来操作next节点，一个指针是用来保存当前节点，使其将next节点的next更新到当前节点。
     */
    IntSLLNode* reverseList(IntSLLNode* head) {
        if (head == 0 || head->next == 0) {
            return head;
        }

        IntSLLNode* newHead = 0;
        IntSLLNode* node;
        while (head != 0) {
            node = head;
            head = head->next;

            node->next = newHead;
            newHead = node;
        }

        return head = node;
    }

3、反转部分单向链表

/**
     * 反转部分单向链表
     * @param head
     * @param from
     * @param to
     * @return
     * 
     * 思路：
     * 跟整体单向链表反转思路，一样只不过需要记住前一个的节点，因为前面有剩余的链表。
     */
    IntSLLNode* reverseListPart(IntSLLNode* head, int from , int to) {
        if (head == 0 || head->next == 0)  {
            return head;
        }
        int hStep = 1;
        IntSLLNode* originNode = head;
        IntSLLNode* pre;
        IntSLLNode* newHead = NULL;
        while (hStep != from) {
            head = head->next;
            hStep++;

            if (hStep == from - 1) {
                pre = head;
            }
        }

        IntSLLNode* node;
        IntSLLNode* newTail;
        while (hStep != (to + 1)) {
            if (hStep == from) {
                newTail = head;
            }

            node = head;
            head = head->next;

            node->next = newHead;
            newHead = node;

            hStep++;
        }

        if (head != 0) {
            pre->next = node;
            newTail->next = head;
        }

        return originNode;
    }