public void relocateList(ListNode head) {// 头结点 ListNode p1 = new ListNode(0); ListNode p2 = new ListNode(0); ListNode pre = null; ListNode pTemp = null; p1.next = head.next; p2.next = head.next; // 单链表为空或有3个元素以内(少于4个),直接返回此单链表即可 if (head.next == null || head.next.next == null || head.next.next.next == null|| head.next.next.next.next==null) return; int length = 0, start2 = 0; // 取得单链表长度 while (p2.next != null) { length++; p2.next = p2.next.next; }// while(p2.next!=null) start2 = length / 2; p2.next = head.next; while (start2 > 0 && p2.next != null) { pre = p2.next; p2.next = p2.next.next; start2--; }// while(start2>0) // 合并左右半区 pre.next = null;// 得到左半区 start2 = length / 2; while (start2 > 0) { // 左半区操作不用另考虑,右半区的结点插入过来即可 pre = p1.next;// 插入结点时要用到pre p1.next = p1.next.next; // 处理右半区结点,头插法 pTemp = p2.next; p2.next = p2.next.next; pTemp.next = p1.next; pre.next = pTemp; // p1.next = p1.next.next; start2--; }// while(start2>0) if (p2.next != null) { pTemp.next=p2.next; }// if(p2.next!=null) }
//完整程序,放入Eclipse即可运行 class ListNode { public int val; ListNode next = null; ListNode(int val) { this.val = val; } public int getValue(){ return this.val; } public void displayNode(){ System.out.print(getValue()+" "); } } class LinkList{ ListNode head; public void insertHead(int val){ ListNode newNode=new ListNode(val); newNode.next=head; head=newNode; } public int getLength(){ ListNode current=head; int length=0; while(current!=null){ length++; current=current.next; } return length; } public void display(){ ListNode current=head; while(current!=null){ current.displayNode(); current=current.next; } } } public class Solution { /** * 按照左右半区的方式重新组合单链表 * 输入:一个单链表的头节点head * 将链表调整成题目要求的样子 * * 后台的单链表节点类如下: **/ static void relocateList(ListNode head) { LinkList list=new LinkList(); list.head=head; ListNode current=head; ListNode otherHead=null; ListNode temp1=null; ListNode temp2=null; int i=0; while(current!=null){ if(i==list.getLength()/2-1){ otherHead=current.next; current.next=null; } i++; current=current.next; } current=otherHead; while(current!=null){ if(head.next==null){ head.next=current; break; } else{ temp1=head.next; head.next=current; temp2=current.next; current.next=temp1; current=temp2; head=temp1; } } } public static void main(String[] args){ LinkList list=new LinkList(); list.insertHead(5); list.insertHead(4); list.insertHead(3); list.insertHead(2); list.insertHead(1); //list.display(); //System.out.println(); relocateList(list.head); list.display(); } }
void relocateList(struct ListNode* head) {
public class Solution { /** * 按照左右半区的方式重新组合单链表 * 输入:一个单链表的头节点head * 将链表调整成题目要求的样子 * * 后台的单链表节点类如下: * public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */ public static void relocateList(ListNode head) { //1.快慢指针找到中间点 ListNode hh = new ListNode(-1);//没分清“头部节点”的补救措施 hh.next = head; ListNode l1,lmid,locate;//locate定位节点 l1 = hh; lmid = hh; int length = 0; for(;l1.next!=null;l1 = l1.next){ length++; if(length%2 == 0) lmid = lmid.next; } if(length > 3) { locate = lmid; lmid = lmid.next;//lmid及以后的都是R locate.next = null; l1 = hh.next; while (l1 != null) { locate = l1; l1 = l1.next; locate.next = lmid; locate = lmid; if (l1 != null) { lmid = lmid.next; locate.next = l1; } } } } }反正过了。。。
typedef struct node{//定义节点类型 int data; struct node * next; }node; void ExchangeList(node *head,int n)//交换函数 { node *left,*right,*q,*p; int i; right=head;q=head->next; for(i=1;i<(n/2);i++){//先找到中间结点 right=q; q=q->next; } printf("right的节点值:%5d\n",right->data); printf("q的节点值 :%5d\n",q->data); left=head;p=head->next; for(int i=0;i<(n/2)-1;i++){//完成交换 left->next=q; right->next=q->next; q->next=p; left=p;p=p->next; q=right->next; } } void Print(node *h)//打印函数 { for(node *p=h;p;p=p->next){ printf("%5d",p->data); } printf("\n"); } int main(void) { node *p,*tail; int n=7; node *head=(node *)malloc(sizeof(node)); head->data=1; head->next=NULL;tail=head; for(int i=0;i<n-1;i++){ p=(node *)malloc(sizeof(node)); p->data=i+2; p->next=NULL; tail->next=p;tail=p; } Print(head); ExchangeList(head,n); printf("The finall answer:"); Print(head); system("pause"); return 0; }
class Solution { public: /** * 按照左右半区的方式重新组合单链表 * 输入:一个单链表的头节点head * 将链表调整成题目要求的样子 * * 后台的单链表节点类如下: * struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */ void relocateList(struct ListNode* head) { int n=0; struct ListNode *l1=(struct ListNode *)malloc(sizeof(struct ListNode)); l1=head; while(l1!=NULL){ n++; l1=l1->next; } l1=head; struct ListNode *l2=(struct ListNode *)malloc(sizeof(struct ListNode)); struct ListNode *l3=(struct ListNode *)malloc(sizeof(struct ListNode)); struct ListNode *l4=(struct ListNode *)malloc(sizeof(struct ListNode)); l2=l1->next; l3=l1; int i=1; while(i<n/2){ l3=l3->next; i++; } l4=l3->next; i=1; while(i<n/2){ l3->next=l4->next; l4->next=NULL; l4->next=l1->next; l1->next=l4; l1=l1->next->next; l4=l3->next; i++; } //free(l4); //free(l3); //free(l2); //free(l1); } };