程序员面试攻略_百度百科
http://baike.baidu.com/link?url=egiDevITF7mxrqaIMf804VbBrCWIwaBsL5QgGZPgb_TfdhRuBZaYXcnLoL-sD7AjX-US4vhW0Zc7eZjWNAYOx_
第4章 链表
- 更新头指针。
- bool insertInFront1(ListNode *pInHead, int inVal)只是对*pInHead进行值传递，然后在函数内更新了头指针的“本地拷贝”。
- 要更新指针可以有两种方式：bool insertInFront2(ListNode **pInHead, int inVal)就是传入了头指针的指针，ListNode *insertInFront3(ListNode *pInHead, int inVal)则是直接返回新的头指针。
- 注意只是传入头指针的话，直接传递pHead。如果是头指针的指针，则是&pHead。
1 #include2 using namespace std; 3 4 struct ListNode 5 { 6 int val; 7 ListNode *next; 8 ListNode(int x = 0) : val(x), next(NULL) {} 9 }; 10 11 class Solution 12 { 13 public: 14 void PrintList(ListNode *inListNode) 15 { 16 if (inListNode != NULL) { 17 cout << inListNode->val << endl; 18 PrintList(inListNode->next); 19 } else 20 cout << "NULL\n" << endl; 21 } 22 23 bool insertInFront1(ListNode *pInHead, int inVal) 24 { 25 cout << "Entry bool insertInFront1(ListNode *pInHead, int inVal)\n" << endl; 26 27 if (pInHead == NULL) return false; 28 29 ListNode *pNewElem = new ListNode; 30 pNewElem->val = inVal; 31 pInHead = pNewElem; // Incorret! 32 33 cout << "pNewElem = " << pNewElem << endl; 34 cout << "PrintList(pNewElem)" << endl; 35 PrintList(pNewElem); 36 37 cout << "pInHead = " << pInHead << endl; 38 cout << "PrintList(pInHead)" << endl; 39 PrintList(pInHead); 40 41 return true; 42 } 43 44 bool insertInFront2(ListNode **pInHead, int inVal) 45 { 46 cout << "Entry bool insertInFront2(ListNode **pInHead, int inVal)\n" << endl; 47 48 if (pInHead == NULL) return false; 49 50 ListNode *pNewElem = new ListNode; 51 pNewElem->val = inVal; 52 *pInHead = pNewElem; // Correctly updates head 53 54 cout << "pNewElem = " << pNewElem << endl; 55 cout << "PrintList(pNewElem)" << endl; 56 PrintList(pNewElem); 57 58 cout << "pInHead = " << pInHead << endl; 59 cout << "PrintList(pInHead)" << endl; 60 PrintList(*pInHead); 61 62 return true; 63 } 64 65 ListNode *insertInFront3(ListNode *pInHead, int inVal) 66 { 67 cout << "Entry ListNode *insertInFront3(ListNode *pInHead, int inVal)\n" << endl; 68 69 if (pInHead == NULL) return false; 70 71 ListNode *pNewElem = new ListNode; 72 pNewElem->val = inVal; 73 74 cout << "pNewElem = " << pNewElem << endl; 75 cout << "PrintList(pNewElem)" << endl; 76 PrintList(pNewElem); 77 78 cout << "pInHead = " << pInHead << endl; 79 cout << "PrintList(pInHead)" << endl; 80 PrintList(pInHead); 81 82 return pNewElem; // Correctly updates head 83 } 84 }; 85 86 int main () 87 { 88 Solution testSolution; 89 int value = 5; 90 91 ListNode* pHead = new ListNode(1); 92 93 cout << "Test bool insertInFront1(ListNode *pInHead, int inVal)\n" << endl; 94 // Print Head node 95 cout << "pHead = " << pHead << endl; 96 if (pHead != NULL) 97 cout << "pHead->val = " << pHead->val << endl; 98 cout << endl; 99 100 // Print Linkedlist101 cout << "PrintList(pHead)" << endl;102 testSolution.PrintList(pHead); 103 104 bool flag = testSolution.insertInFront1(pHead, value);105 cout << "testSolution.insertInFront1(pHead, value) = " << flag << "\n" << endl;106 107 // Print Head node108 cout << "pHead = " << pHead << endl;109 if (pHead != NULL)110 cout << "pHead->val = " << pHead->val << endl;111 cout << endl;112 113 // Print Linkedlist114 cout << "PrintList(pHead)" << endl;115 testSolution.PrintList(pHead); 116 117 delete pHead;118 pHead = NULL;119 120 cout << "Test bool insertInFront2(ListNode **pInHead, int inVal)\n" << endl;121 122 pHead = new ListNode(2);123 124 // Print Head node125 cout << "pHead = " << pHead << endl;126 if (pHead != NULL)127 cout << "pHead->val = " << pHead->val << endl;128 cout << endl;129 130 // Print Linkedlist131 cout << "PrintList(pHead)" << endl;132 testSolution.PrintList(pHead); 133 134 flag = testSolution.insertInFront2(&pHead, value);135 cout << "testSolution.insertInFront2(&pHead, value) = " << flag << "\n" << endl;136 137 // Print Head node138 cout << "pHead = " << pHead << endl;139 if (pHead != NULL)140 cout << "pHead->val = " << pHead->val << endl;141 cout << endl;142 143 // Print Linkedlist144 cout << "PrintList(pHead)" << endl;145 testSolution.PrintList(pHead); 146 147 delete pHead;148 pHead = NULL;149 150 cout << "Test ListNode *insertInFront3(ListNode *pInHead, int inVal)\n" << endl;151 152 pHead = new ListNode(3);153 154 // Print Head node155 cout << "pHead = " << pHead << endl;156 if (pHead != NULL)157 cout << "pHead->val = " << pHead->val << endl;158 cout << endl;159 160 // Print Linkedlist161 cout << "PrintList(pHead)" << endl;162 testSolution.PrintList(pHead); 163 164 pHead = testSolution.insertInFront3(pHead, value);165 166 // Print Head node167 cout << "pHead = " << pHead << endl;168 if (pHead != NULL)169 cout << "pHead->val = " << pHead->val << endl;170 cout << endl;171 172 // Print Linkedlist173 cout << "PrintList(pHead)" << endl;174 testSolution.PrintList(pHead); 175 176 delete pHead;177 pHead = NULL;178 179 getchar();180 181 return 0;182 }
- 遍历链表时，要不断的检查它的末尾。 E.g. head != NULL
- 删除链表
- 注意删除顺序，指针移动赋值
1 #include2 using namespace std; 3 4 struct ListNode 5 { 6 int val; 7 ListNode *next; 8 ListNode(int x = 0) : val(x), next(NULL) {} 9 };10 11 class Solution 12 {13 public:14 void PrintList(ListNode *inListNode)15 {16 if (inListNode != NULL) {17 cout << inListNode->val << endl;18 PrintList(inListNode->next);19 } else20 cout << "NULL" << endl;21 }22 23 // Assign in ptr of the head ptr24 void DeleteList(ListNode **pInHead)25 {26 ListNode *pDel = *pInHead;27 28 while (pDel != NULL)29 {30 // Reserve the address of the next node31 ListNode *pNext = pDel->next; 32 // Delete the current node33 delete pDel;34 pDel = NULL;35 // Move to the next node36 pDel = pNext;37 }38 39 // Set head to NULL 40 *pInHead = NULL;41 }42 };43 44 int main ()45 {46 Solution testSolution;47 int count = 10;48 49 ListNode *pHead = NULL;50 ListNode *pCur = NULL;51 52 for (int i = 0; i < count; i ++)53 {54 ListNode *pTemp = new ListNode(i);55 56 if (i == 0)57 pHead = pCur = pTemp;58 else {59 pCur->next = pTemp;60 pCur = pCur->next; // pCur->next == pTemp61 }62 }63 64 // Print Head 65 cout << "pHead = " << pHead << endl;66 if (pHead != NULL)67 cout << "pHead->val = " << pHead->val << endl;68 cout << endl;69 70 // Print Linkedlist71 cout << "PrintList(pHead)" << endl;72 testSolution.PrintList(pHead); 73 74 cout << "Test DeleteList(pHead)\n" << endl; 75 testSolution.DeleteList(&pHead);76 77 // Print Head 78 cout << "pHead = " << pHead << endl;79 if (pHead != NULL)80 cout << "pHead->val = " << pHead->val << endl;81 cout << endl;82 83 // Print Linkedlist84 cout << "PrintList(pHead)" << endl;85 testSolution.PrintList(pHead); 86 87 getchar();88 89 return 0;90 }