单链表相关问题 - 高飞网
52 人阅读

单链表相关问题

2016-12-16 22:37:41

删除给定结点,要求O(1)时间复杂度

思路

    正常情况下,如果我们想删除某个节点,由于结点是单向的,因此首先要查找到该结点在链表中的位置,如下图所示,如果想删除结点q,那么我们先要找到它的前继结点p,通过将前继结点p的指向域指向q->next,来把q结点删除。因为这里涉及到查找,因此时间复杂度为O(n)。

    观察上面的结点,现在假如我们知道了q结点,要删除它不简单,我们不知道它的前继结点p。但是想删除q->next结点却很简单,只要将q结点的指针域指向q->next->next就可以了。

    本来我们要删除q,现在q无法删除,我们可以删q-next,但最终结果我们是要保存q-next的,因此我们可以把q-next的数据和指针都送给q,这样q相当于是q-next的替身,删了q-next和删q效果一样。

代码实现

//O(1)时间删除链表节点,从无头单链表中删除节点
void deleteRandomNode(Node *cur)
{
    assert(cur != NULL);
    assert(cur->next != NULL);    //不能是尾节点
    Node* pNext = cur->next;
    cur->data = pNext->data;
    cur->next = pNext->next;
    delete pNext;
}


单链表的转置

思路

    链表的转置是一个很常见、很基础的数据结构题了,非递归的算法很简单,用三个临时指针 pre、head、next 在链表上循环一遍即可。递归算法也是比较简单的,但是如果思路不清晰估计一时半会儿也写不出来吧。

代码实现

//单链表的转置,循环方法
Node* reverseByLoop(Node *head)
{
    if(head == NULL || head->next == NULL)
        return head;
    Node *pre = NULL;
    Node *next = NULL;
    while(head != NULL)
    {
        next = head->next;

        head->next = pre;
        pre = head;
        head = next;
    }
    return pre;
}

//单链表的转置,递归方法
Node* reverseByRecursion(Node *head)
{
    //第一个条件是判断异常,第二个条件是结束判断
    if(head == NULL || head->next == NULL) 
        return head;

    Node *newHead = reverseByRecursion(head->next);

    head->next->next = head;
    head->next = NULL;

    return newHead;    //返回新链表的头指针
}


求单链表倒数第k个结点

思路

设置两个指针 p1、p2,首先 p1 和 p2 都指向 head,然后 p2 向前走 k 步,这样 p1 和 p2 之间就间隔 k 个节点,最后 p1 和 p2 同时向前移动,直至 p2 走到链表末尾。

代码实现


//倒数第k个节点
Node* theKthNode(Node *head,int k)
{
    if(k < 0) return NULL;    //异常判断

    Node *slow,*fast;
    slow = fast = head;
    int i = k;
    for(;i>0 && fast!=NULL;i--)
    {
        fast = fast->next;
    }

    if(i > 0)    return NULL;    //考虑k大于链表长度的case

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

    return slow;
}


求链表的中间结点

思路

    此题的解决思路和第3题「求链表的倒数第 k 个节点」很相似。可以先求链表的长度,然后计算出中间节点所在链表顺序的位置。但是如果要求只能扫描一遍链表,如何解决呢?最高效的解法和第3题一样,通过两个指针来完成。用两个指针从链表头节点开始,一个指针每次向后移动两步,一个每次移动一步,直到快指针移到到尾节点,那么慢指针即是所求。

代码实现


//求链表的中间节点
Node* theMiddleNode(Node *head)
{
    if(head == NULL)
        return NULL;
    Node *slow,*fast;
    slow = fast = head;
    //如果要求在链表长度为偶数的情况下,返回中间两个节点的第一个,可以用下面的循环条件
    //while(fast && fast->next != NULL && fast->next->next != NULL)  
    while(fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}




还没有评论!
54.204.219.143