鹅厂是一家能让你拥有多元化职业发展的平台。尊重个性、轻松自在的工作环境、有趣的互联网工作。在鹅厂这家拥有海量用户基础的公司工作,能得到互联网应用最前沿的视野、获得好的专家辅导。小编从今天开始就会陆续作死挑战鹅厂面试题,并持续为大家更新!
题目
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
思路
单链表,官方释义为:是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。如图:
单链是单向的,只能单向访问,现需要将链表翻转过来,也就是说next指针要反向。
1、简单思路:
当然这里有个简单的思路:遍历一遍链表,将每个元素都存储进vector容器,然后反向迭代vector的每个元素,并将元素的next指针指向容器中前一个元素。这是最简单的方式,实现起来也十分好理解;
ListNode* reverseList(ListNode* head) { if(head == NULL)return NULL; vector<ListNode*> vec ; ListNode* node_head = head ; while (node_head->next!=NULL) { vec.push_back(node_head); node_head = node_head->next ; } vec.push_back(node_head); auto iter = vec.rbegin(); while (iter != vec.rend()) { if(iter+1!=vec.rend())(*iter)->next = *(iter+1); else (*iter)->next = NULL ; iter ++ ; } return node_head; }
但是这种方式并不是鹅厂想要的,因为他们想考的是面试者对链表数据结构的理解程度,以及逻辑思维的深度。
2、从链表角度的思路
单链表反转,我们需要处理的就是当前节点、当前节点前一个节点、当前节点后一个节点,这三个节点之间的逻辑关系(node_head、node_temp_pre、node_temp_next)。其实我们只需要将头指针逐步顺着链表往后移,并且在移动过程中,改变next的指向。
思路实现关键点:
首先我们得在改变当前节点next指向之前将next指向的节点访问出来并通过指针保存起来,不然当当前节点的next指向改变再来访问就访问不到了
然后将next指向node_temp_pre(之前保存的前一个节点)
再然后要做好准备将head往后移动一位,将当前节点赋值给node_temp_pre,作为后续节点的next节点
最后移动head
题解
ListNode* reverseList(ListNode* head) { if(head == NULL)return NULL; ListNode* node_head = head ; ListNode* node_temp_pre = NULL ; ListNode* node_temp_next = NULL ; while(node_head->next!=NULL) { node_temp_next = node_head->next; node_head->next = node_temp_pre ; node_temp_pre = node_head ; node_head = node_temp_next; } node_head->next = node_temp_pre; return node_head; }