《数据结构与算法分析：C语言描述》复习——第三章“线性表、栈和队列”—

《数据结构与算法分析：C语言描述》复习——第三章“线性表、栈和队列”——单向链表

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 }