2014.06.14 21:40

简介：

　　单向链表应该是绝大多数C语言初学者学会的第一个结构体了。每个节点会指向后续节点，属于顺序结构。由于单链表的实现简单，并且有着明显的限制，使其成为各种天才面试官们虐小朋友的利器（链表的功能实在很有限，而面试官总是要求你用链表完成各种各样的任务，难度就在这儿了）。因此，随手写链表肯定是参加面试的底线了，否则你都没机会动笔就可以回家等消息了。

图示：

　　

实现：

1 // My implementation for singly linked list.  2 struct ListNode {  3     int val;  4     ListNode *next;  5     ListNode(int _val = 0): val(_val), next(nullptr) {};  6 };  7   8 class SinglyLinkedList {  9 public: 10     SinglyLinkedList() { 11         m_size = 0; 12         m_head = nullptr; 13         m_tail = nullptr; 14     } 15      16     void insertFront(int val) { 17         if (m_size == 0) { 18             m_head = m_tail = new ListNode(val); 19         } else { 20             ListNode *ptr = new ListNode(val); 21             ptr->next = m_head; 22             m_head = ptr; 23         } 24         ++m_size; 25     } 26      27     void insertBack(int val) { 28         if (m_size == 0) { 29             m_head = m_tail = new ListNode(val); 30         } else { 31             m_tail->next = new ListNode(val); 32             m_tail = m_tail->next; 33         } 34         ++m_size; 35     } 36      37     void insertNode(int pos, int val) { 38         int i; 39          40         if (i <= 0) { 41             insertFront(val); 42         } else if (i >= m_size) { 43             insertBack(val); 44         } else { 45             ListNode *ptr1, *ptr2; 46              47             ptr1 = m_head; 48             for (i = 0; i < pos - 1; ++i) { 49                 ptr1 = ptr1->next; 50             } 51             ptr2 = new ListNode(val); 52             ptr2->next = ptr1->next; 53             ptr1->next = ptr2; 54             ++m_size; 55         } 56     } 57      58     void deleteNode(int pos) { 59         if (pos < 0 || pos > m_size - 1) { 60             return; 61         } 62          63         ListNode *ptr1, *ptr2; 64         if (pos == 0) { 65             ptr1 = m_head; 66             if (m_size == 1) { 67                 m_head = m_tail = nullptr; 68             } else { 69                 m_head = m_head->next; 70             } 71             delete ptr1; 72         } else { 73             ptr1 = m_head; 74             for (int i = 0; i < pos - 1; ++i) { 75                 ptr1 = ptr1->next; 76             } 77             ptr2 = ptr1->next; 78             ptr1->next = ptr2->next; 79             if (ptr2->next == nullptr) { 80                 m_tail = ptr1; 81             } 82             delete ptr2; 83         } 84         --m_size; 85     } 86      87     void updateNode(int pos, int val) { 88         if (pos < 0 || pos > m_size - 1) { 89             return; 90         } 91          92         ListNode *ptr = m_head; 93         for (int i = 0; i < pos; ++i) { 94             ptr = ptr->next; 95         } 96         ptr->val = val; 97     } 98      99     ListNode *findNode(int val) {100         ListNode *ptr = m_head;101         while (ptr != nullptr) {102             if (ptr->val == val) {103                 return ptr;104             }105             ptr = ptr->next;106         }107         108         return nullptr;109     }110     111     ~SinglyLinkedList() {112         ListNode *ptr = m_head;113         while (m_head != nullptr) {114             m_head = m_head->next;115             delete ptr;116             ptr = m_head;117         }118         m_head = m_tail = nullptr;119     }120 private:121     int m_size;122     ListNode *m_head;123     ListNode *m_tail;124 };125 126 int main()127 {128     return 0;129 }