数据结构 【单链表练习】

        今天来探讨两个练习题要使用的思想为快慢指针。

        1、返回链表的中间节点

        给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

        整体思路如下图所示：

        代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* fast,*slow;
    fast = slow = head;

    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }

    return slow;
    
}

        2、返回链表中倒数第k个值

        实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

        整体思路如下：

        代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
int kthToLast(struct ListNode* head, int k) {
    struct ListNode* slow,*fast;
    slow = fast = head;

    while(--k)
    {
        fast = fast->next;
    }

    while(fast->next)
    {
        slow = slow->next;
        fast = fast->next;
    }

    return slow->val;
}

3、反转链表

        三指针逐个反转链表的指向，思路如下图所示：

        代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    if(head == NULL)
        return head;
    struct ListNode* n1,*n2,*n3;
    n1 = NULL;
    n2 = head;
    n3 = n2->next;

    while(n2)
    {
        if(n3 == NULL)
        {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            break;
        }
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        n3 = n3->next;
    }
    return n1;
}

方法2：顺序取出每一个节点，头插到新的链表中，思路如下：

        代码实现：

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

    while(cur)
    {
        cur->next = newHead;

        newHead = cur;
        cur = next;
        if(next != NULL)
            next = next->next;


    }
    return newHead;
}

4、合并两个有序链表

        将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。思路如下图所示：

        代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if(list1 == NULL)
    {
        return list2;
    }
    if(list2 == NULL)
    {
        return list1;
    }
    struct ListNode* head,*tail;
    head = tail = NULL;
    struct ListNode* cur1 = list1,*cur2 = list2;

    while(cur1 && cur2)
    {
        if(cur1->val <= cur2->val)
        {
            if(head == NULL)
            {
                head = cur1;
                tail = cur1;
            }
            else
            {
                tail->next = cur1;
                tail = tail->next;
            }
            cur1 = cur1->next;
        }else
        {
            if(head == NULL)
            {
                head = cur2;
                tail = cur2;
            }
            else
            {
                tail->next = cur2;
                tail = tail->next;
            }
            cur2 = cur2->next;
        }
    }

    if(cur1)
    {
        tail->next = cur1;
    }
    if(cur2)
    {
        tail->next = cur2;
    }
    return head;
}