24/07/10数据结构(4.1209)单链表OJ

链表常见题目

1.删除链表中给定值val的值(这个题最好能自己完全写出来)(该题耗时半个多小时)

输入:1->2->6->3->4->5->6, val = 6

输出:1->2->3->4->5

/*

 Definition for singly_linked list.

 struct ListNode{

 int val;

 struct ListNode* next;//结构体指针

 }

*/

struct ListNode* remoceElements(struct listNode* head, int val){

    struct ListNode* prev = NULL, *cur = head;

    while (cur){

        if (cur->val == val){

            //非头结点

            if (prev != NULL){

                prev->next = cur->next;

            }

            else{

                //头结点,更新头结点

                head = cur->next;

            }

            LisrNode* next = cur->next;

            //删除当前节点

            free(cur);

            //更新到下一个节点

            cur = next;

        }

        else{

            prev = cur;

            cur = cur->next;

        }

    }

    return head;

}

2.反转一个单链表

示例:输入:1->2->3->4->5->NULL

        输出:NULL->5->4->3->2->1

思路:空链表:元素头插.NULL,1插进去做新的head,依次...

node->next = new head;newhead = node;

/*

 Definition for singly_linked list.

 struct ListNode{

 int val;

 struct ListNode* next;

 }

*/

struct ListNode* reversrList(struct ListNode* head){

    struct ListNode* newHead = NULL;

    struct ListNode* cur = head;

    while (cur){

        //保存下一个节点的位置

        struct ListNode* next = cur->next;

        //头插

        cur->next = newHead;

        newHead = cur;

        //头插下一个数据

        cur = next;

    }

    return newHead;

}

3.给定一个带有头结点head的非空单链表,返回链表的中间节点.如果有两个中间节点,则返回第二个中间节点.

思路:不使用遍历两次的方法,使用快慢指针(一个指针一次走两步,一个指针一次走一步)

/*

 Definition for singly_linked list.

 struct ListNode{

 int val;

 struct ListNode* next;

 }

*/

struct ListNode* middleNode(struct ListNode* head){

    struct ListNode* fast = head;

    struct ListNode* slow = head;

    while (fast && fast->nest){

        fast = fast->next->next;

        slow = slow->next;

    }

    return slow;

}

 

4.输入一个链表,输出该链表中倒数第k个节点

思路:依然不使用循环在输出(n-k),还是用两个指针,让一个先走k次再同时走输出走的比较少的.

struct ListNode* FindkthToTail(struct ListNode* pListHead, int k){

    struct ListNode* fast, *slow;

    fast = slow = pListHead;

    while (k--){

        if (fast)

            fast = fast->nest;

        else

            return NULL;

    }

    while (fast){

        fast = fast->nest;

        slow = slow->nest;

    }

    return slow;

}

5.将两个有序链表合并为一个新的有序链表并返回.新链表是通过拼接给定的两个链表的所有节点组成的.

示例:输入:1->2->4, 1->3->4

        输出:1->1->2->3->4->4

struct ListNode* mergeTowLists(struct ListNode* l1, struct ListNode* l2){

    if (l1 == NULL)

        return l2;

    if (l2 == NULL)

        return l1;

    struct ListNode* newHead, *newTail;

    //确定表头

    if (l1->val <= l2->val){

        newHead = newTail = l1;

        l1 = l1->nest;

    }

    else{

        newHead = newTail = l2;

        l2 = l2->nest;

    }

    //合并,新的节点插入表尾

    while (l1 && l2){

        if (l1->val <= l2->val){

            newTail->next = l1;

            l1 = l1->next;

            newTail = newTail->next;

        }

        else{

            newTail->next = l2;

            l2 = l2->next;

            newTail = newTail->next;

        }

    }

    //合并剩余的节点

    if (l1)

        newTail->next = l1;

    if (l2)

        newTail->next = l2;

    return newHead;

}

6.编写代码,以给定值x为基准将链表分割成两部分,所有小于x的节点排在大于或等于x的节点之前.

ListNode* partition(ListNode* pHead, int x){

    struct ListNode* lessHead, *lessTail, *greaterHead, *greaterTail, *cur;

    lessHead = lessTail = greaterHead = greaterTail = NULL;

    cur = pHead;

    while (cur){

        if (cur->val < x){

            //判断是否为空链表

            if (lessHead == NULL)

                lessHead = lessTail = cur;

            else{

                lessTail->nest = cur;

                lessTail = lessTail->next;

            }

        }

        else{

            if (greaterHead == NULL)

                greaterHead = greatTail = cur;

            else{

                greaterTail->next = cur;

                greaterTail = greaterTail->next;

            }

        }

        cur = cur->next;

    }

}

//链接两个链表

if (lessTail)

    lessTail->next = greatHead;

if (greaterTail)

    greaterTail->next = NULL;

if (lessHead)

return lessHead;

else

return greaterHead;