Circle In List

发表于 2017-03-16 | 分类于算法

Circle In List(链表中环相关的问题)

题目1描述：

给定一个链表的头结点，判断其是否存在环，如果存在请返回进入环的第一个交点，否则返回空节点。

例子：

1->2->3-4-NULL则返回NULL，1->2->3->4->3则返回节点3。

解题思路：

利用快慢指针的方法可以方便的帮助我们判断链表中是否存在环的问题。首先定义一个快指针，一个慢指针；快指针每次走两步，慢指针每次走一步。如果链表中存在环，则肯定快慢指针会互相碰到。如何找到链表中第一个进入环的节点利用的方法原理如下：我们假设慢节点从开始到与快节点碰到，一共走了n步，则快节点一共走了2n步。通过画图后我们可以知道，慢节点继续走达到环的入口的距离和从头结点到达环入口的节点的距离相同。所以此时只要将快节点重新从头结点出发，当二者重新碰到时即为入口节点。

代码如下：

#include "ListNode.h"
#include<iostream>
using namespace std;
class getLoopNode1{
public:
    ListNode* getLoopNode(ListNode* head){
        ListNode* slow = head;
        ListNode* fast = head; //定义快慢指针
        while(fast->next != NULL && fast->next->next != NULL){
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast)
                break;
        }                    //第一次碰见
        if (fast->next == NULL || fast->next->next == NULL)
            return NULL;
        fast = head;
        while(fast != slow){
            slow = slow->next;
            fast = fast->next;
        }                  //第二次碰见
        return fast;
    }
};

题目2描述：

给定两个无环链表的头结点，判断二者是否相交，如果相交返回相交的节点。否则返回空节点。

例子：

head1的链表为:1->2->3->4->5->NULL;head2的链表为:7->8->9->4->5->NULL。可知其在节点4后相交，即返回节点4。

解题思路：

通过观察我们发现如果链表存在相同的部分，则相同的部分的长度是一样的。那我们只需要找到合适的遍历位置即可找到相交的节点。首先我们分别遍历head1和head2得到链表的长度n1和n2。得到链表长度的差值|n1 - n2| = d;然后我们在较长的链表上先走d步后，再从较短链表的头节点开始遍历，如果二者遇到了相同的节点我们就认为这两个链表相交。

代码如下：


#include "ListNode.h"
#include <iostream>
using namespace std;
class getCommonNode1{
public:
    ListNode* getCommonNode(ListNode* head1, ListNode* head2){
        int length1 = 1;
        int length2 = 1;
        int difference = 0;
        ListNode* cur1 = head1;
        ListNode* cur2 = head2;
        while(cur1->next != NULL){
            cur1 = cur1->next;
            length1++;
        }
        while(cur2->next != NULL){
            cur2 = cur2->next;
            length2++;
        }
        difference = (length1 > length2) ? length1 - length2 : length2 - length1;
        // 分别遍历得到链表的长度和对应的差值
        cur1 = head1;
        cur2 = head2;
        if (length1 > length2){
            while(difference != 0){
                cur1 = cur1->next;
                difference--;
            }
        }else{
            while(difference != 0){
                cur2 = cur2->next;
                difference--;
            }
        } //让较长的链表节点先行遍历
        while(cur1 != cur2){
            cur1 = cur1->next;
            cur2 = cur2->next;
        }  //再二者同时遍历判断公共点
        return cur1;
    }
};

题目3描述：

给定两个有环链表的头结点，判断这个两个链表是否相交，如果相交返回公共节点，否则返回空节点。

解题思路：

根据题目，已经给定这两个链表有环。所以可以根据题目1中的方法，分别找到这两个链表的进入环的节点。而后依情况分析:(1)第一种情况，这两个链表进入环的链表的节点相同，则直接返回该节点即可。(2)如果这两个节点不相同，说明存在两种情况，即这两个链表不相交或者相交但是进入环的节点不同。根据以上分析，该情况下我们可以通过使其中一个节点不断移动的方法，如果是在同一个环内，则一定会相交。反之则不相交。该情况的停止情况为：移动节点移动一圈后如果碰不见另外一个节点即停止。

代码如下：

#include "ListNode.h"
#include "getLoopNode.h"
#include <iostream>
using namespace std;
class bothLoop1{
friend class getLoopNode1;
public:
    ListNode* bothLoop(ListNode* head1, ListNode* head2){
        getLoopNode1 func;
        ListNode* node1 = func.getLoopNode(head1);
        ListNode* node2 = func.getLoopNode(head2);
                       // 找到两个链表的进入环的节点
        if (node1 == node2)
            return node1; 
                       // 两个链表进入节点相同直接返回
        else{
            ListNode* cur = node1->next;
            while(cur != node1){
                if (cur != node2){
                    cur = cur->next;
                }else{
                    return node1;
                      // 移动其中一个节点判断其是否都在环里。
                }
            }
            return NULL;
        }
    }
};

题目4描述：

约瑟夫环问题:即在一个长度为m由链表节点构成的环中，按照规则，每n个节点将其删除，求返回的最后剩下的那个链表节点。

解题思路：

解题的思路很直接，从头遍历环链表，利用报数变量，来将第n个节点删除。需要主义的地方是，我们需要记录上一个节点才能将当前节点删除；另外删除的终止的条件在与当当前节点的下一个节点的是本身的时候，说明环中只剩下一个节点。返回该节点即可。(另有利用数学规律可以直接找到剩下节点待诉)

代码如下：

#include "ListNode.h"
class josephusKill1{
public:
    ListNode* josephusKill(ListNode* head, int m){
        if (head == NULL || head->next == head || m < 1)
            return head;
        int count = 0;
        ListNode* last = head;
        while(last->next != head){
            last = last->next;
        }                  // 找到头节点的上一个节点
        while(head != last){
            if (++count == m){
                last->next = head->next;
                count = 0; //删除当前节点并清空报数
            }else{
                last = last->next;
            }
            head = last->next;
        }
        return head;
    }
};

AddLists

发表于 2017-03-15 | 分类于算法

AddLists(将两个链表相加)

题目描述：

两个链表中保存中一系列整数，分别代表着两个整数；例如1->2->3；给定两个链表的头结点，返回两个链表中数相加后的结果。

例子：

例如给定1->2->3和2->4->5;则返回头结点，其指向的链表内容为3->6->8。

解题思路：

解题思路为：因为数据的相加需要从尾部开始，所以第一个想法是利用栈结构。将数据分别导入到两个栈中，不断的从栈顶提取出数据，相加后新建一个节点，用相加的初始值初始化该节点，并记录是否进位；下一次的相加后的新建的节点指向上一个节点即可。另外也可以将结果导入到一个新栈中，在全部计算完成之后，从栈顶取元素初始化即可。

代码如下：

其中关于链表类的定义如下：

struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x): val(x), next(NULL) {};
};

解法一：利用三个栈来实现，需要注意的是进位的保存和计算完成之后需要判断进位来决定头结点是否为1.

#include "ListNode.h"
#include "reverseList.h"
#include <stack>
using namespace std;
class addLists1{
public:
    ListNode* addLists(ListNode* head1, ListNode* head2) {
        stack<int> stk1;
        stack<int> stk2;
        stack<int> stk3;
        int n1 = 0;
        int n2 = 0;
        int ca = 0;
        while (head1 != NULL) {
            stk1.push(head1->val);
            head1 = head1->next;
        }                      //第一链表数据进栈
        while (head2 != NULL) {
            stk2.push(head2->val);
            head2 = head2->next;
        }                     //第二个链表数据进栈
        while (!stk1.empty() || !stk2.empty()) {
            n1 = stk1.empty() ? 0 : stk1.top();
            stk1.pop();
            n2 = stk2.empty() ? 0 : stk2.top();
            stk2.pop();
            stk3.push((n1 + n2 + ca) % 10);
            ca = ((n1 + n2 + ca) >= 10) ? 1 : 0;
        }                    //相加结果进栈保存
        ListNode* pre = new ListNode(-1);
        ListNode* cur = pre;
        while (!stk3.empty()) {
            cur->next = new ListNode(stk3.top());
            stk3.pop();
            cur = cur->next;
        }                   //将栈中元素初始化并连接
        if (ca == 1){
            pre->val = 1;
            return pre;
        }                   //最后判断最高位是否存在进位
        else
            return pre->next;
    }
};

解法二：直接将链表逆序后计算和的值并连接链表

class addLists2{
public:
    ListNode* addLists(ListNode* head1, ListNode* head2){
        reverseList1 re;
        head1 = re.reverseList(head1);
        head2 = re.reverseList(head2);//链表的逆序处理
        int n1 = 0;
        int n2 = 0;
        int ca = 0;
        ListNode* cur = new ListNode(-1);
        ListNode* backup = cur;
        while(head1 != NULL || head2 != NULL){
            n1 = (head1 == NULL) ? 0 : head1->val;
            n2 = (head2 == NULL) ? 0 : head2->val;
            cur->next = new ListNode((n1 + n2 + ca) % 10);
            ca = (n1 + n2 + ca>= 10) ? 1 : 0;
            cur = cur->next;         //从头开始相加并记录进位
            head1 = (head1 == NULL) ? NULL : head1->next;
            head2 = (head2 == NULL) ? NULL : head2->next;
        }                           
        if (ca == 1){
            cur->next = new ListNode(1);
        }                           //判断最高位的进位
        cur = backup->next;
        backup->next = NULL;
        cur = re.reverseList(cur); //将结果逆序后返回
        return cur;
    }
};