寻找链表中倒数第K个结点的位置

链表中尾数第K个结点,倒数结点

主题材料:搜索单链表中尾数第K个结点.

其大器晚成题貌似平日据悉?

输入叁个链表,输出该链表中尾数第K个结点。

难题:输入三个链表,输出该链表中尾数第K个结点。为了相符超越五中年人的习于旧贯,本题从1始发计数,即链表的尾结点是尾数第三个结点。比如一个链表有6个结点,从头结点起首它们的值依次是1、2、3、4、5、6。那一个链表的尾数第四个结点是值为4的结点。

思路:设定七个指针p1和p2,三个指针刚开端都指向链表的首先个结点,然后让p1指针先走(k-1)步,然后再让八个指针一同以后走,当p1指针指向链表最终贰个结点的时候,p2指针正好指向链表中的倒数第k个结点。

在写代码的时候须要思量鲁棒性,最佳使用防范性编程,就是思考在哪些地点会出错,然后提前抬高错误判别,那样幸免由此错误输入而以致程序崩溃。

  1 #include<iostream>
  2 #include<stdio.h> 
  3 #include<tchar.h>
  4 using namespace std;
  5 
  6 //链表结构
  7 struct ListNode
  8 {
  9     int m_nValue;
 10     ListNode* m_pNext;
 11 };
 12 
 13 //创建一个链表结点
 14 ListNode* CreateListNode(int value)
 15 {
 16     ListNode* pNode = new ListNode();
 17     pNode->m_nValue = value;
 18     pNode->m_pNext = NULL;
 19 
 20     return pNode;
 21 }
 22 
 23 //输出链表中的某一结点的值
 24 void PrintListNode(ListNode* pNode)
 25 {
 26     if(pNode == NULL)
 27             printf("The node is NULL\n");
 28     else
 29             printf("The key in node is %d.\n", pNode->m_nValue);
 30 }
 31 
 32 //输出链表 
 33 void PrintList(ListNode* pHead)
 34 {
 35     ListNode *pNode = pHead;
 36     while(pNode != NULL)
 37     {
 38         cout << pNode->m_nValue<< " ";
 39         pNode = pNode->m_pNext;
 40     }
 41     cout<<endl;
 42 }
 43 
 44 //删除结点 
 45 void DestroyList(ListNode* pHead)
 46 {
 47     ListNode* pNode = pHead;
 48     while(pNode != NULL)
 49     {
 50         pHead = pHead->m_pNext;
 51         delete pNode;
 52         pNode = pHead;
 53     }
 54 }
 55 
 56 //往链表末尾添加结点
 57 /*
 58 注意这里pHead是一个指向指针的指针,在主函数中一般传递的是引用。
 59 因为如果要为链表添加结点,那么就会修改链表结构,所以必须传递引用才能够保存修改后的结构。
 60 */
 61 void AddToTail(ListNode** pHead, int value)
 62 {
 63     ListNode* pNew = new ListNode();
 64     pNew->m_nValue = value;
 65     pNew->m_pNext = NULL;
 66 
 67     if(*pHead == NULL)
 68     {
 69         *pHead = pNew;
 70     }
 71     else
 72     {
 73         ListNode* pNode = *pHead;
 74         while(pNode->m_pNext != NULL)
 75             pNode = pNode->m_pNext;
 76 
 77         pNode->m_pNext = pNew;
 78     }
 79 }
 80 
 81 
 82 //链接两个结点 
 83 //void ConnectListNodes(ListNode* pCurrent, ListNode* pNext)
 84 //{
 85 //    if(pCurrent == NULL)
 86 //    {
 87 //        printf("Error to connect two nodes.\n");
 88 //        exit(1);
 89 //    }
 90 //    pCurrent->m_pNext = pNext;
 91 //}
 92 
 93 //防御性编程,鲁棒性更好
 94 ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)
 95 {
 96     if(pListHead == NULL || k == 0)
 97             return NULL;
 98 
 99     ListNode *pAhead = pListHead;
100     ListNode *pBehind = NULL;
101 
102     for(unsigned int i = 0 ; i < k- 1 ; i ++)
103     {
104         if(pAhead->m_pNext != NULL)
105             pAhead = pAhead->m_pNext;
106         else
107             return NULL;
108     }
109     
110     pBehind = pListHead;
111     while(pAhead->m_pNext != NULL)
112     {
113         pAhead = pAhead->m_pNext;
114         pBehind = pBehind->m_pNext;
115     }
116 
117     return pBehind;
118 }
119 
120 int main()
121 {
122     //创建结点
123     ListNode* pNode1=CreateListNode(1);//创建一个结点
124     PrintList(pNode1);//打印
125     //往链表中添加新结点
126     AddToTail(&pNode1, 2);//为链表添加一个结点
127     AddToTail(&pNode1, 3);//为链表添加一个结点
128     AddToTail(&pNode1, 4);//为链表添加一个结点
129     AddToTail(&pNode1, 5);//为链表添加一个结点
130     AddToTail(&pNode1, 6);//为链表添加一个结点
131     AddToTail(&pNode1, 7);//为链表添加一个结点
132     //打印链表
133     PrintList(pNode1);//打印
134     //反转链表
135     ListNode* KthNode=FindKthToTail(pNode1,3);
136 
137     PrintListNode(KthNode);
138 
139     DestroyList(pNode1);
140     
141     return 0;
142 }

图片 1

标题:输入一个链表,输出该链表中尾数第K个结点。为了顺应大多数人的习贯,本题从1上马计数,即链表…

中央代码:
<pre><code>` func nthToLastNode(node:ListNode,k:Int) ->
ListNode? {
if k <= 0 {
return nil
}

七个指针,指针1指向头,指针2指向头+k的职责,指针2达到后面部分的时候指针1就是答案

图片 2

    var p1:ListNode? = node
    var p2:ListNode? = node

    for _ in 0..<k - 1 {
        if p2 == nil {
            return nil
        }
        p2 = p2?.next
    }

    if p2 == nil {
        return nil
    }

    while p2?.next != nil {
        p1 = p1?.next
        p2 = p2?.next
    }

    return p1
}`</code></pre>

图片 3图片 4

 1 struct ListNode 
 2 {
 3     int m_nValue;
 4     ListNode* m_pNext;
 5 };
 6 ListNode* FindKthToTail(ListNode* pListHead , unsigned int K)
 7 {
 8     if (!pListHead || K <=0)
 9     {
10         return NULL ;
11     }
12     ListNode* pAhead = pListHead;
13     ListNode* pBehind = NULL ;
14     for (int i=1 ; i != K ;i++)
15     {
16         if (pAhead->m_pNext != NULL)
17         {
18             pAhead = pAhead->m_pNext ;
19         }
20         else
21         {
22             return NULL;
23         }        
24     }
25     pBehind = pListHead ;
26     while(pAhead->m_pNext != NULL)
27     {
28         pAhead = pAhead->m_pNext ;
29         pBehind = pBehind->m_pNext;
30     }
31     return pBehind ;
32 }

测量试验代码:
<pre><code>var nthNode:ListNode? = listNodeManger.nthToLastNode(node: listNodeManger.headNode!, k: 3) if nthNode != nil { print("FlyElephant--倒数的k个节点:\(nthNode!.value!)") }</code></pre>

/*
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* ph = pListHead, *pf = pListHead;
        for(int i = 0; ph && i < k - 1; ++i){
            ph = ph->next;
        }
        if(ph == nullptr)
            return nullptr;
        while(ph->next){
            ph = ph->next;
            pf = pf->next;
        }
        return pf;
    }
};

 

View Code

 

相关文章