有一个链表，其中每个对象包含两个指针p1, p2，其中指针p

[问答题]

有一个链表，其中每个对象包含两个指针p1, p2，其中指针p1指向下一个对象，指针p2也指向一个对象，沿p1可以像普通链表一样完成顺序遍历，沿p2则可能会有重复。一种可能的例子如下，其中实线箭头是p1, 虚线箭头是p2：

问题：设计函数，翻转这个链表，并返回头指针。链表节点的数据结构如下：

struct Node{
    Node * p1;
    Node * p2;
    int data;
};

函数定义如下：

Node * revert(Node* head);

666的佩奇爸爸

#include<iostream>
#include<map>
using namespace std;

struct Node
{
    int data;
    Node* p1;
    Node* p2;
    Node(int d):data(d),p1(NULL),p2(NULL){}
};
Node* reverse(Node* pHead)
{
    map<Node*,Node*>p2Relation;
    Node* pReversedHead=NULL;
    Node* pNode=pHead;
    Node* pPrev=NULL;
    //翻转p1
    while(pNode!=NULL)
    {
        Node* pNext=pNode->p1; 
        if(pNext!=NULL)
            pReversedHead=pNode;
        p2Relation.insert(pair<Node*,Node*>(pNode,pNode->p2));
        pNode->p1=pPrev;
        pPrev=pNode;
        pNode=pNext;
    }
    //翻转p2指针
    map<Node*,Node*>::iterator it;
    for(it=p2Relation.begin();it!=p2Relation.end();++it)
        it->second->p2=it->first;
    return pReversedHead;
}

发表于 2018-06-03 20:20:10 回复(0)

牛客733423号

#include<iostream>
using namespace std;

typedef struct Node
{
struct Node* p1;
struct Node *p2;
int data;
}node;

//克隆链表
node* newHead(node *head)
{
if(head == NULL)
{
  return NULL;
}
node* p = head->p1;
while(p)
{
  //创建新节点
  node* newnode = (node *)malloc(sizeof(node));
  memset(newnode,'0',sizeof(node));
  newnode->p1 = p->p1;
  newnode->p2 = NULL;
  newnode->data = p->data;
  p->p1 = newnode;
  p = newnode->p1;
}
return head;
}
//复制p2指针
void connectNodes(node* head)
{
node* pNode = head->p1;
while(pNode != NULL)
{
  node* pCloned = pNode->p1;
  if(pNode->p2 != NULL)
  {
   pCloned->p2 = pNode->p2->p1;
  }
  pNode = pCloned->p1;
}
}

//带头节点的链表的反转
node* revert(node* head)
{
node* pNode = head;
node* p = pNode->p1 ;
node *q;

pNode = NULL;

while(p)
{
  q = p->p1;
  p->p1 = pNode;
  pNode = p;
  p = q;
}
head->p1 = pNode;

return head;
}

//反转p2指针

void connectNodes(node* head)
{
node* pNode = head->p1;
while(pNode != NULL)
{
  node* pCloned = pNode->p1;
  if(pNode->p2 != NULL)
  {
   pCloned->p2 = NULL;
   pNode->p2->p1->p2 = pCloned;
  }
  pNode = pCloned->p1;
}
}

还有一部链表拆分改天再续。。。

发表于 2015-04-26 02:35:18 回复(1)

大漠苍鹰

该题思路为：首先利用p1进行指针的翻转，在这个顺序遍历的过程中，使用HashMap记录当前节点的p2指向关系，并以当前节点为key，将指向的那个节点为Value存入Map。由于每个节点只有一个p2，因此key唯一。

当p1全部翻转完之后，对Hashmap进行遍历，由于key和value直接表明了指向与被指向的关系，因此可以直接修改key的p2，进行反转即可。

代码如下：

class Node{
    Node p1,p2;
    int data;
}
public class Reverse_List {
    HashMap<Node, Node> hashMap = new HashMap<Node, Node>();
    public void reverse(Node head){
        Node pre = head;
        Node cur = head.p1;
        Node realTail = cur;
        while(cur!=null){
            Node next = cur.p1;
            cur.p1 = pre;
            pre = cur;

            if(cur.p2!=null)
                hashMap.put(cur,cur.p2);

            cur = next;

        }
        head.p1 = pre;
        realTail.p1 = null;
        Set<Map.Entry<Node, Node>> entry = hashMap.entrySet();
        for(Map.Entry<Node, Node> entry1:entry){
            Node a = entry1.getKey();
            Node b = entry1.getValue();
            b.p2 = a;
        }
    }
}

发表于 2015-02-19 14:09:42 回复(1)