程序员面试金典Chapter2

第一题输出链表中的倒数第n个结点

给出的结构体为：

struct ListNode {

  int val;

  struct ListNode *next;

  ListNode(int x) :

  val(x), next(NULL) {

    }
};

我觉得首先应该要把整个链表的长度先求出来，然后在不判断不遍历整个链表的情况下只比对数字。下面是示例代码：

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        ListNode* temp = pListHead;
        int count=0;
        while(temp){
            count++;
            temp=temp->next;
        }
        for(int i=0;i<count;){
            if(i == count-k){
                return pListHead;
                break;
            }
            pListHead=pListHead->next;
            i++;
        }
        return NULL;
    }
};

第二题删除单向链表中的一个节点

我觉得删除节点分两步，一个是删除单向链表中上一个只想该节点的链接和该节点指向下一个节点的链接，而变成第n-1个节点->next指向原先的n+1个节点。第二步就是当删除了链接并不代表当前删除的节点不占用内存空间，所以就要free这个空间。下面是通过的代码示例：

class Remove {
public:
    bool removeNode(ListNode* pNode) {
        // write code here
        if(pNode->next == NULL)
            return false;
        ListNode* temp=pNode->next;
        pNode->next=temp->next;
        free(temp);
        return true;
    }
};

第三题分割链表

题目描述的是要将小于给定x值的节点与大于x值的节点分割成两部分，而本身链表的顺序不能够改变。最后需要返回小于x值的链表+大于x值的链表的头节点。想法很单纯，既然要分割链表就自然需要定义两个新的链表，第一步遍历整个给定的链表将每个节点的值与给定的x值作对比，当小于x的时候就把新定义的p1链表的下一个节点指向此时的temp节点，而当大于x值得时候自然就将此时的temp节点赋给p2的下一个节点。在过程中需要保存两个新定义链表的表头，也就是要判断一下p1和p2的头结点以便最后返回头节点。下面为最终的代码示例：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        ListNode* p1 = NULL;
        ListNode* p2 = NULL;
        ListNode* temp = NULL;
        ListNode* p1Head = NULL;
        ListNode* p2Head = NULL;
        while(pHead){
            temp = pHead->next;
            if(pHead->val<x){
                if(p1 == NULL){
                    p1=pHead;
                    p1Head=pHead;
                }
                   
                else{
                  p1->next=pHead;
                  p1=p1->next;  
                }
            }
            else{
                if(p2 == NULL){
                   p2=pHead;
                    p2Head=pHead;
                }
                    
                else{
                	p2->next=pHead;
                	p2=p2->next; 
                }   
            }
            pHead=temp;
        }
        if(p2)
            p2->next=NULL;
        if(p1 == NULL)
            p1Head=p2Head;
        else
            p1->next=p2Head;
        return p1Head;
    }
};

第四题链表A+B

题目描述为相加两个给出的链表A与B，比如说：{1,2,3} + {3,2,1}需要返回一个结果链表为{4,4,4}。在中间的加法运算中主要分为两步，第一步计算每每两个数字相加的结果，第二部提取出相应结果的进位和需要保留的个位数结果。下面为这一部分实现的代码示例：

val1 = a?a->val:0;
val2 = b?b->val:0;
int val = val1 + val2+carry;
carry = val/10;

定义两个新的ListNode结构的新链表，一个用来做最后返回的链表头，一个作为链表的存储。因为不知道两个给定的链表长度，所以判断的时候两个链表都判断是否为NULL再进入循环来遍历两个链表。当遍历时判断一下最终返回链表的头节点，下面为完整的代码示例：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Plus {
public:
    ListNode* plusAB(ListNode* a, ListNode* b) {
        // write code here
        ListNode* pNode = NULL;
        ListNode* pHead = NULL;
        int carry=0;
        if(a == NULL && b == NULL)
            return NULL;
        while(a || b || carry>0){
            int val1,val2;
            val1 = a?a->val:0;
            val2 = b?b->val:0;
            int val = val1 + val2+carry;
            carry = val/10;
            
            ListNode* temp = new ListNode(val%10);
            if(pNode == NULL){
                pNode = temp;
                pHead = pNode;
            }
            else{
                pNode->next = temp;
                pNode=pNode->next;
            }
            a=a?a->next:NULL;
            b=b?b->next:NULL;
        }
        pNode->next = NULL;
        return pHead;
    }
};

第五题回文链表

题目描述是这样的，需要判断一个给定的链表是否为回文链表，若给定链表如{1,2,3,2,1}则返回true，反之返回false。想法应该说并不难，但是我在链表的地址和赋值之间来回徘徊了很久才大概明白代码测试一直不能通过是因为什么，下面先来看这个代码

class Palindrome {
public:
    bool isPalindrome(ListNode* pHead) {
        // write code here·
        ListNode* reverseNode = NULL;
        ListNode* originalNode = pHead;
        ListNode* temp = NULL;
        ListNode* next = NULL;
        if(pHead == NULL)
            return false;
        while(pHead){
            next = pHead->next;
            temp = reverseNode;//temp=current
            reverseNode = pHead;//prev=current
            reverseNode->next = temp;//next=current
            pHead = next;
        }
        while(originalNode && reverseNode){
            if(originalNode->val != reverseNode->val){
                return false;
                break;
            }
            originalNode = originalNode->next;
            reverseNode = reverseNode->next;
        }
        return true;
    }
};

首先定义了两个链表节点分别指向第一个给定节点和NULL，然后遍历给定的链表将链表反转。在遍历的过程中，将reverse这个想象中是反转后的链表先传给一个temp以做保留，将reverse指向遍历当前的节点，而reverse->next指向先前的地址也就是temp，然而此时我想也就破坏了给定链表指向next的这个节点链接了。先贴一个正常反转链表并返回反转之后链表表头的leetcode上通过的代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp,*current,*next;
        ListNode* reverse = NULL;
        current = head;
        //prev = NULL;
        while(current){
            next = current->next;
            temp = reverse;
            reverse = current;
            reverse->next = temp;
            current = next;
        }
        return reverse;
    }
};

同样将这段代码整齐的贴进这道题再去遍历做比较，依然会不能通过测试，始终返回true，以我的专业出身和智商还没有真正深究出原因，不过我猜想是因为永远指向同一个地址那么比较的时候肯定会不如人意，当在反转时有必要将反转之后的链表reverse和在遍历当前给定链表的时候new一个新的ListNode而不是在同一条地址链上进行多次的重复操作以至于最后比对的original链表丢失。这也是为什么当只是单纯做反转链表的时候遍历第一步就要保存好当前节点next指向的地址。所以重新定义并new一个链表reverse为NULL，然后遍历整个给定的链表，将当前节点值给该次循环中的reverse节点，将该被改动的reverse节点的next指向上一循环中的reverse节点，以此类推，直到把NULL推到最后一个位置。这个方法我很熟悉，跟做硬件编译时传输10101010….类的数据相差不大，都是按照一定的顺序你推我我推你到穷尽。

这里很想插一句

一直以来人们给所谓程序员配的图满是10101010…..，看黑客帝国就知道了，我想说没错，计算机是接受二进制，可是在我自学Nodejs开发和这些满满的上层软件面向对象碰到过10101010现象的机会远远不如我作为公司的一名新晋嵌入式开发来的平常。

程序员分很多种，我希望我哪种都不是，我不是一名程序员或者软件、硬件工程师，我只是一名普通人，懂得少学得慢。

好吧，插了一句嘴，下面来贴上纠结了我一下午的最终通过代码示例：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Palindrome {
public:
    bool isPalindrome(ListNode* pHead) {
        // write code here
        
        ListNode* temp = NULL;
        ListNode* current = pHead;
        ListNode* reverse = new ListNode(NULL);
        if(pHead == NULL)
            return false;
        while(current){
            //temp = reverse;
            //reverse->next = temp;
            //reverse = current->next;
            temp=reverse;
            ListNode* nextnode = new ListNode(current->val);//reverse = current->next;
            reverse = nextnode;
            reverse->next = temp;
            current = current->next;
        }
         
        while(pHead){
            if(pHead->val!=reverse->val)
                {
                return false;
                break;
            }
                
            pHead=pHead->next;
            reverse=reverse->next;
        }
        return true;
    }
};

第一题 输出链表中的倒数第n个结点

第二题 删除单向链表中的一个节点

第三题 分割链表

第四题 链表A+B