首页 > 代码库 > 算法题——翻转链表中的一段
算法题——翻转链表中的一段
题目：给出一个链表中的两个指针p1和p2，将其之间的结点翻转。
思路：可以通过交换结点内的值来实现结点的翻转，空间为O(N)；如果要求不能交换值，那么仅凭p1和p2是无法翻转的，只能交换两个指针之间的链表。
代码：
交换值：
1 struct ListNode 2 { 3 int val; 4 ListNode *next; 5 }; 6 7 void reverseNodes(ListNode *p1, ListNode *p2) { 8 if ( p1 == NULL || p2 == NULL ) 9 return;10 11 vector<ListNode*> nodes;12 for(vector<ListNode*>::iterator p = p1; ; p = p->next ) {13 nodes.push_back(p);14 if ( p == p2 ) 15 break;16 }17 18 int i = 0, j = nodes.size() - 1;19 while ( i<j ) 20 swap(nodes[i++]->val, nodes[j--]->val);21 }
交换结点：
1 void reverseNodes(ListNode *p1, ListNode *p2) { 2 if ( p1 == NULL || p1->next == NULL ) 3 return; 4 5 ListNode *pre = p1->next, *cur = pre->next; // 6 7 while ( cur != p2 && cur != NULL ) 8 { 9 ListNode *tmp = cur->next;10 cur->next = pre;11 pre = cur;12 cur = tmp;13 }14 15 p1->next->next = cur;16 p1->next = pre;17 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。