首页 > 试题广场 >

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

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

问题:设计函数,翻转这个链表,并返回头指针。链表节点的数据结构如下:
struct Node{
    Node * p1;
    Node * p2;
    int data;
};
函数定义如下:
Node * revert(Node* head);

#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)

#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)
羽头像
Node * revert(Node * head)
{
    Node * x;
    Node * y;
    x=head;
    head=x->p2;x->p2=x->p1;x->p1=NULL;
    y=head;
    while(y->p2!=NULL){
        y->p1=y->p2;
        y->p2=x;
        x=y;
        y=x->p1;
        }
    return head;
}
发表于 2014-11-25 20:16:36 回复(0)