链表奇偶位置调换

时间：2025-02-15 17:44:18

题目：将链表的奇数位和偶数位调换组成新的链表

分析：先遍历链表，将链表依据奇数位和偶数位分解成两个链表，然后依次在偶数位链表中的每个结点后面插入奇数位链表中的相应位置的每个结点。定义两个函数，一个是删除链表头结点，另一个是在指定结点后面插入一个节点。重组链表的过程即是删除奇数位链表头结点，然后再将其插入在偶数位链表中指定的位置上。

时间复杂度为O(N)

/*
 * 将链表的奇数位和偶数位调换组成新链表
 */
#include <>

struct Node {
    int   m_nValue;
    Node* m_pNext;
};


Node* DeleteHeadNode(Node** pHead) {
	if (!pHead || *pHead == NULL) return NULL;
	Node* pNode = *pHead;
	*pHead = pNode->m_pNext;
	pNode->m_pNext = NULL;
	return pNode;
}


void InsertAfterNode(Node* pNode, Node* pInsertedNode) {
	if (!pNode) return;
	pInsertedNode->m_pNext = pNode->m_pNext;
	pNode->m_pNext = pInsertedNode;
}

链表拆分：

Node* SeperateList(Node* pHead) {
    if (!pHead) return NULL;
    Node* pNode = pHead;
    Node* pNext = pNode->m_pNext;
    Node* pEvenHead = pNext; // second list head in even position
    while (pNext) {
        pNode->m_pNext = pNext->m_pNext;
        pNode = pNext;
        pNext = pNext->m_pNext;
    }
    return pEvenHead;
}

链表重建：

void RebuildList(Node** pHead) {
    if (!pHead || *pHead == NULL) return;
    Node* pOddNode = *pHead;
    Node* pEvenNode = SeperateList(pOddNode);
    if (!pEvenNode) {  // list has one node
        *pHead = pOddNode;
        return;
    }
    *pHead = pEvenNode;
    
	while (pEvenNode && pOddNode) {
		Node* pNode = DeleteHeadNode(&pOddNode);
		InsertAfterNode(pEvenNode, pNode);
		if (!pNode->m_pNext)
			break;
		pEvenNode = pNode->m_pNext;
	}
	if (pOddNode) {  // numbers of nodes in oddlist > numbers of nodes in evenlist
		pEvenNode->m_pNext->m_pNext = pOddNode;
	}
}

注意：涉及指针的参数传递需要注意一些地方，比如是传递指针（Node*）还是传递指针的指针（Node**)，自己的一点认识是，

1、如果在函数体内部有对指针本身（即指针指向的地址如pHead，非指针指向地址的内容如pHead->m_pNext等）做修改，而且函数体外部需要反应这种变化，就一定要用指针的指针，比如上述的DeleteHeadNode(), RebuidList()；

2、如果函数体内只是对指针指向的内容作修改，并不对指针本身的指向（的地址）作修改，即没有类似pHead = pOtherPointer的改变，传递指针即可，而且在函数体内部对指针的内容作出的修改，如pHead->m_nValue = 0，在函数体外也会反应出来，如上述的SeperateList(), InsertAfterNode()，这是因为指针指向的地址不变，在函数外部访问该指针指向的内存时，内存内容的变化是可以被读到的。

3、参数传递指针如Node*，在函数体内对其做修改也是没有意义的，因为这只是一个传值（而非传地址和传引用），函数体内部做的改变在函数体外部是不可见的，函数体外部会变回原来的值，如同基本的数据类型，所以只有对其指向的内容操作才是有意义的。若要函数体外反应出函数体内对指针的改变，就要传地址Node**（指针的地址）或传引用Node*&（指针的引用）。

4、指针的指针有时不容易理解，可以将指针重新定义一下，就可以按基本数据类型的定义来理解了，如：typedef Node* pNode;我们在传递参数的时候就可以如下定义了pNode pHead; pNode* pHead;或者pNode& pHead;第一种定义在函数体内的变化，在外部无法体现，也即传值；而后两者可以反应这种变化，即传地址和传引用（引用即别名，指向同一块内存）。

5、将指针的指向（也即地址），同指针指向的内存（也即内容），分开来考虑就会容易理解上述参数传递的问题。

参考：

[1]/sunnyskyliu/article/details/8099402

相关文章