基础题:
1、删除一个无头单链表的非尾结点
思路:一般单链表结点的删除需要知道要删结点的前一个结点然后进行删除,但现在是无头单链表即不能从头结点开始遍历,寻找它的前一个结点,此时已知的是要删结点的位置,可利用交换数值来删除;
代码:
void RemoveNode(ListNode* pnode)
{assert(pnode);ListNode* next = pnode->_next;pnode->_data = next->_data ;pnode->_next = next->_next ;delete next;
}
2、从尾到头打印单链表
思路:利用递归思想来实现
代码:
void ReversePrint(ListNode* l)
{ListNode* cur = l;if(cur == NULL)return ;if(cur->_next){ReversePrint(cur->_next);}cout<<cur->_data<<" ";
}
附加题:
复杂链表的复制,一个链表的每个节点,有一个指向下一个结点的next指针,还有一个random指针指向这个链表中的一个随机结点或者NULL,现在要求复制这个链表,返回复制后的新链表
复杂链表的结构:
typedef struct ComplexNode
{
DataType _data;
struct ComplexNode* _next;
struct ComplexNode* _random; //指向随机结点(可以是链表中的任意一点或为空)
}ComplexNode;