链表的交错重排L1,Ln,L2,Ln

2024-02-08 00:44| 来源: 网络整理| 查看: 265

其实一开始并没有想到时间上O(n)的方法，想到了也是空间复杂度是O(n)的(需要用到栈或者递归)：链表分两段，用栈记录第一段的遍历过程。

后来经提示想到了，可以将第二段链表逆序。从而不需要额外的辅助空间，在O(n)完成。

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: //Divide the list into two parts first length n-n/2, second length n/2, reverse serconde part. //Insert each node in second list into first list. void reorderList(ListNode *head) { if(NULL == head || NULL == head -> next) return; //divide ListNode *p1 = head; ListNode* p2 = head -> next; for(; p2 != NULL;p1 = p1 -> next, p2 = p2 -> next){ p2 = p2 -> next; if(p2 == NULL) break; } ListNode* temp = p1; p1 = p1 -> next; temp -> next = NULL; //reverse second list ListNode *pre = p1; if(p1 -> next != NULL){ ListNode* p = p1 -> next; temp = NULL; p1 -> next = NULL; while(p != NULL){ temp = p; p = p -> next; temp -> next = pre; pre = temp; } } ListNode* secHead = pre; //Insert node in second list into first list ListNode* p = head; ListNode* temp2 = NULL; while(secHead != NULL){ temp = p -> next; temp2 = secHead; p -> next = temp2; secHead = secHead -> next; temp2 -> next = temp; p = temp; } } }; 含测试的代码： #include struct ListNode { int m_nValue; ListNode *next; ListNode(int x) : m_nValue(x), next(NULL) {} ListNode(){} }; ListNode* CreateListNode(int value) { ListNode* pNode = new ListNode(); pNode->m_nValue = value; pNode->next = NULL; return pNode; } void ConnectListNodes(ListNode* pCurrent, ListNode* pNext) { if(pCurrent == NULL) { printf("Error to connect two nodes.\n"); //exit(1); } pCurrent->next = pNext; } void PrintListNode(ListNode* pNode) { if(pNode == NULL) { printf("The node is NULL\n"); } else { printf("The key in node is %d.\n", pNode->m_nValue); } } void PrintList(ListNode* pHead) { printf("PrintList starts.\n"); ListNode* pNode = pHead; while(pNode != NULL) { printf("%d\t", pNode->m_nValue); pNode = pNode->next; } printf("\nPrintList ends.\n"); } void DestroyList(ListNode* pHead) { ListNode* pNode = pHead; while(pNode != NULL) { pHead = pHead->next; delete pNode; pNode = pHead; } } void AddToTail(ListNode** pHead, int value) { ListNode* pNew = new ListNode(); pNew->m_nValue = value; pNew->next = NULL; if(*pHead == NULL) { *pHead = pNew; } else { ListNode* pNode = *pHead; while(pNode->next != NULL) pNode = pNode->next; pNode->next = pNew; } } void RemoveNode(ListNode** pHead, int value) { if(pHead == NULL || *pHead == NULL) return; ListNode* pToBeDeleted = NULL; if((*pHead)->m_nValue == value) { pToBeDeleted = *pHead; *pHead = (*pHead)->next; } else { ListNode* pNode = *pHead; while(pNode->next != NULL && pNode->next->m_nValue != value) pNode = pNode->next; if(pNode->next != NULL && pNode->next->m_nValue == value) { pToBeDeleted = pNode->next; pNode->next = pNode->next->next; } } if(pToBeDeleted != NULL) { delete pToBeDeleted; pToBeDeleted = NULL; } } void DestroyNode(ListNode* pNode) { delete pNode; pNode = NULL; } void reorderList(ListNode *head) { if(NULL == head || NULL == head -> next) return; //divide ListNode *p1 = head; ListNode* p2 = head -> next; for(; p2 != NULL;p1 = p1 -> next, p2 = p2 -> next){ p2 = p2 -> next; if(p2 == NULL) break; } ListNode* temp = p1; p1 = p1 -> next; temp -> next = NULL; //reverse second list ListNode *pre = p1; if(p1 -> next != NULL){ ListNode* p = p1 -> next; temp = NULL; p1 -> next = NULL; while(p != NULL){ temp = p; p = p -> next; temp -> next = pre; pre = temp; } } ListNode* secHead = pre; //Insert node in second list into first list ListNode* p = head; ListNode* temp2 = NULL; while(secHead != NULL){ temp = p -> next; temp2 = secHead; p -> next = temp2; secHead = secHead -> next; temp2 -> next = temp; p = temp; } } int main(){ ListNode* pNode1 = CreateListNode(1); ListNode* pNode2 = CreateListNode(2); ListNode* pNode3 = CreateListNode(3); ListNode* pNode4 = CreateListNode(4); ListNode* pNode5 = CreateListNode(5); ListNode* pNode6 = CreateListNode(6); ListNode* pNode7 = CreateListNode(7); ConnectListNodes(pNode1, pNode2); ConnectListNodes(pNode2, pNode3); ConnectListNodes(pNode3, pNode6); ConnectListNodes(pNode4, pNode5); ConnectListNodes(pNode5, pNode6); ConnectListNodes(pNode6, pNode7); PrintList(pNode1); reorderList(pNode1); PrintList(pNode1); DestroyNode(pNode1); DestroyNode(pNode2); DestroyNode(pNode3); DestroyNode(pNode4); DestroyNode(pNode5); DestroyNode(pNode6); DestroyNode(pNode7); return 0; }

【本文地址】

公司简介

联系我们