The result of tag: (10 results)

Linked List - Linked List Cycle II

by LauCyun Sep 22,2014 15:30:42 4,352 views

Question

Problem Statement

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Example

Given1->2->3->4->5->6, tail connects to node index 2, return 3.

题解 - 快慢指针

这题 Linked List - Linked List Cycle 的升级版,首先假设组成环的节点个数为\(r\),链表中节点个数为\(n\)

首先我们来分析下在链表有环时都能推出哪些特性:

  1. 快慢指针第一次相遇时快指针比慢指针多走整数个环, 这个容易理解,相遇问题。
  2. 每次相遇都在同一个节点。第一次相遇至第二次相遇,快指针需要比慢指针多走一个环的节点个数,而快指针比慢指针多走的步数正好是慢指针自身移动的步数,故慢指针恰好走了一圈回到原点。

从以上两个特性可知,在仅仅知道第一次相遇时的节点还不够,相遇后如果不改变既有策略则必然找不到环的入口。

接下来我们分析如何从第一次相遇的节点走到环的入口节点。还是先从实际例子出发,以下图为例:

slowfast节点分别初始化为节点12,假设快慢指针第一次相遇的节点为\( C_i\),那么此时慢指针正好走了\(n-r+i-1\)步,快指针则走了\(2(n-r+i-1)\)步,快慢指针第一次相遇时慢指针肯定没有走完整个环,且慢指针走的步数即为整数个环节点个数,由性质1和性质2可联合推出:

\((n-r+i-1)+1=x \cdot r\)  (\(x\)为非负整数)      式1

为什么在后面加1?是因为快指针初始化时多走了一步

现在分析下相遇的节点和环的入口节点之间的关联,要从环中第i个节点走到环的入口节点,则按照顺时针方向移动的节点数:

\(x \cdot r - i+1\)    (\(x\)为非负整数)             式2

由式1可以推知:\(n-r=x \cdot r-i\),也就是说从头节点走到环的入口节点所走的步数\(n-r\)

如果快慢指针第一次相遇时让快指针从头节点出发,慢指针仍从当前位置迭代,为了让快慢指针在环的入口点相遇,由式1和式2可以推知:需要让慢指针先走一步,否则会出现死循环。

C:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
/**
 * @param head: The first node of linked list.
 * @return: The node where the cycle begins.
 *          if there is no cycle, return null
 */
struct ListNode *detectCycle(struct ListNode *head) {
    if (NULL == head || NULL == head->next) {
        return NULL;
    }

    struct ListNode *slow = head, *fast = head->next;
    while (NULL != fast && NULL != fast->next) {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) {
            slow = slow->next;
            fast = head;
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }
            return fast;
        }
    }
    return NULL;
}

源码分析

  1. 异常处理。
  2. 找第一次相遇的节点。
  3. 先将slow先走一步,然后将fast置为头节点,并只走一步,直至快慢指针第二次相遇,返回慢指针所指的节点。

复杂度分析

第一次相遇的最坏时间复杂度为\( O(n)\),第二次相遇的最坏时间复杂度为\( O(n)\),故总的时间复杂度近似为\( O(n)\),空间复杂度\( O(1)\)

Reference

...

Tags Read More


Linked List - Linked List Cycle

by LauCyun Sep 22,2014 10:01:24 5,012 views

Question

Problem Statement

Given a linked list, determine if it has a cycle in it.

Example

Given1->2->3->4->5, tail connects to node index 1, return true.

题解 - 快慢指针

对于带环链表的检测,效率较高且易于实现的一种方式为使用快慢指针。快指针每次走两步,慢指针每次走一步,如果快慢指针相遇(快慢指针所指内存为同一区域)则有环,否则快指针会一直走到NULL为止退出循环,返回false

快指针走到NULL退出循环即可确定此链表一定无环这个很好理解。那么带环的链表快慢指针一定会相遇吗?先来看看下图。

在有环的情况下,最终快慢指针一定都走在环内,加入第i次遍历时快指针还需要k步才能追上慢指针,由于快指针比慢指针每次多走一步。那么每遍历一次快慢指针间的间距都会减少1,直至最终相遇。故快慢指针相遇一定能确定该链表有环。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef enum { false, true } bool;

/**
 *
 * @param head: The first node of linked list.
 * @return: True if it has a cycle, or false
 */
bool hasCycle(struct ListNode *head) {
    if (NULL == head || NULL == head->next) {
        return false;
    }

    struct ListNode *slow = head, *fast = head;
    while (NULL != fast && NULL != fast->next) {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) {
            return true;
        }
    }
    return false;
}

源码分析

  1. 异常处理,将head->next也考虑在内有助于简化后面的代码。
  2. 慢指针初始化为head, 快指针初始化为head的下一个节点,这是快慢指针初始化的一种方法,有时会简化边界处理,但有时会增加麻烦,比如该题的进阶版。

复杂度分析

  1. 在无环时,快指针每次走两步走到尾部节点,遍历的时间复杂度为\( O(\frac{n}{2})\).
  2. 有环时,最坏的时间复杂度近似为 \(O(n)\). 最坏情况下链表的头尾相接,此时快指针恰好在慢指针前一个节点,还需 n 次快慢指针相遇。最好情况和无环相同,尾节点出现环。

故总的时间复杂度可近似为\(O(n)\).

Reference

...

Tags Read More


Linked List - Reverse Linked List

by LauCyun Sep 20,2014 18:04:26 3,639 views

Question

Problem Statement

Reverse a linked list.

Example

For linked list 1->2->3, the reversed linked list is 3->2->1

题解1 - 非递归

分析由1->2->3变为3->2->1的过程,由于是单向链表,故只能由1开始遍历,1和2最开始的位置是1->2,最后变为2->1,故从这里开始寻找突破口,探讨如何交换1和2的节点:

temp = head->next;
head->next = prev;
prev = head;
head = temp;

要点在于维护两个指针变量prevhead, 翻转相邻两个节点之前保存下一节点的值,分析如下图所示:

可归纳为:

  • 保存head下一节点
  • 将head所指向的下一节点改为prev
  • 将prev替换为head,波浪式前进
  • 将第一步保存的下一节点替换为head,用于下一次循环

C

/**
 * 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 *prev = NULL, *temp = NULL;
    while (head != NULL) {
        temp = head->next;
        head->next = prev;
        prev = head;
        head = temp;
    }
    // fix head, because head is NULL at this time
    head = prev;
    return head;
}

源码分析

题解中基本分析完毕,代码中的prev赋值比较精炼,值得借鉴。

复杂度分析

遍历一次链表,时间复杂度为\(O(n)\),使用了辅助变量,空间复杂度\(O(1)\)

题解2 - 递归

递归的终止步分三种情况讨论:

  1. 原链表为空,直接返回空链表即可。
  2. 原链表仅有一个元素,返回该元素。
  3. 原链表有两个以上元素,由于是单链表,故翻转需要自尾部向首部逆推。

由尾部向首部逆推时大致步骤为先翻转当前节点和下一节点,然后将当前节点指向的下一节点置空(否则会出现死循环和新生成的链表尾节点不指向空),如此递归到头节点为止。新链表的头节点在整个递归过程中一直没有变化,逐层向上返回。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *reverseList(struct ListNode *head) {
    // case1: empty list
    if (head == NULL) {
        return NULL;
    }
    // case2: only one element list
    else if (head->next == NULL) {
        return head;
    }
    // case3: reverse from the rest after head
    struct ListNode *newHead = reverseList(head->next);
    // reverse between head and head->next
    head->next->next = head;
    // unlink list from the rest
    head->next = NULL;
    return newHead;
}

源码分析

case1 和 case2 可以合在一起考虑,case3 返回的为新链表的头节点,整个递归过程中保持不变。

复杂度分析

递归嵌套层数为\(O(n)\),时间复杂度为\(O(n)\),空间(不含栈空间)复杂度为\(O(1)\)

Reference

...

Tags Read More


Linked List - Remove Nth Node From End of List

by LauCyun Sep 20,2014 13:46:17 2,821 views

Question

Problem Statement

Given a linked list, remove the nth node from the end of list and return its head.

  •  Notice
    The minimum number of nodes in list is n.

Example

Given linked list: 1->2->3->4->5->null, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5->null.

题解

简单题, 使用快慢指针解决此题,需要注意最后删除的是否为头节点。让快指针先走n步,直至快指针走到终点,找到需要删除节点之前的一个节点,改变slow->next域即可。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

/**
 * Remove Nth Node From End of List.
 *
 * @param head: The first node of linked list.
 * @param n: An integer.
 * @return: The head of linked list.
 */
struct ListNode *
removeNthFromEnd(struct ListNode *head, const int n) {
    if (head == NULL || n < 0) {
        return NULL;
    }

    struct ListNode *fast = head;
    struct ListNode *slow = head;

    int i = 0;
    while (i < n) {
        if (fast == NULL) {
            return NULL;
        }
        fast = fast->next;
        ++i;
    }
    if (fast == NULL) {
        return head->next;
    }

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

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

以上代码单独判断了是否需要删除头节点的情况,在遇到头节点不确定的情况下,引入dummy节点将会使代码更加优雅,改进的代码如下。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

/**
 * Remove Nth Node From End of List.
 *
 * @param head: The first node of linked list.
 * @param n: An integer.
 * @return: The head of linked list.
 */
struct ListNode *
removeNthFromEnd(struct ListNode *head, const int n) {
    if (head == NULL || n < 0) {
        return NULL;
    }

    struct ListNode *dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->val = -1;
    dummy->next = head;
    struct ListNode *curr = dummy;

    int i = 0;
    while (i < n) {
        if (head == NULL) {
            return NULL;
        }
        head = head->next;
        ++i;
    }

    while (head != NULL) {
        head = head->next;
        curr = curr->next;
    }

    curr->next = curr->next->next;
    head = dummy->next;
    free(dummy);
    return head;
}

...

Tags Read More


Linked List - Add Two Numbers

by LauCyun Sep 20,2014 12:58:04 3,859 views

Question

Problem Statement

You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example

Given 7->1->6 + 5->9->2. That is, 617 + 295.

Return 2->1->9. That is 912.

Given 3->1->5 and 5->9->2, return 8->0->8.

题解

一道看似简单的进位加法题,实则杀机重重,不信你不看答案自己先做做看。

首先由十进制加法可知应该注意进位的处理,但是这道题仅注意到这点就够了吗?还不够!因为两个链表长度有可能不等长!因此这道题的亮点在于边界和异常条件的处理,感谢 @wen 引入的 dummy 节点,处理起来更为优雅!

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

/***
 * Create a new list node.
 * @param val: The value of the new node.
 * @return
 */
struct ListNode *
newNode(const int val) {
    struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
    temp->val = val;
    temp->next = NULL;
    return temp;
}

/***
 * You are given two non-empty linked lists representing two non-negative integers.
 * The digits are stored in reverse order and each of their nodes contain a single digit.
 * Add the two numbers and return it as a linked list.
 * You may assume the two numbers do not contain any leading zero, except the number 0 itself.
 *
 * Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
 * Output: 7 -> 0 -> 8
 *
 * @param l1: linked lists.
 * @param l2: linked lists.
 * @return: a linked lists.
 */
struct ListNode *
addTwoNumbers(struct ListNode *l1, struct ListNode *l2) {
    if (l1 == NULL && l2 == NULL) {
        return NULL;
    }
    struct ListNode *dummy = newNode(-1);
    struct ListNode *curr = dummy;
    int carry = 0;
    while ((l1 != NULL) || (l2 != NULL) || (carry > 0)) {
        int l1_val = (l1 != NULL) ? l1->val : 0;
        int l2_val = (l2 != NULL) ? l2->val : 0;
        int sum = carry + l1_val + l2_val;

        carry = (int) (sum / 10);
        curr->next = newNode(sum % 10);

        curr = curr->next;
        if (l1 != NULL) l1 = l1->next;
        if (l2 != NULL) l2 = l2->next;
    }
    curr = dummy->next;
    free(dummy);
    return curr;
}

源码分析

  1. 迭代能正常进行的条件为(l1 != NULL) || (l2 != NULL) || (carry > 0), 缺一不可。
  2. 对于空指针节点的处理可以用相对优雅的方式处理 - int l1_val = (l1 != NULL) ? l1->val : 0;
  3. 生成新节点时需要先判断迭代终止条件(l1 == NULL) && (l2 == NULL) && (carry <= 0), 避免多生成一位数0。 使用 dummy 节点可避免这一情况。

复杂度分析

没啥好分析的,时间和空间复杂度均为\(O(max(L1, L2))\)

...

Tags Read More