欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode143重排链表

程序员文章站 2024-02-04 08:26:46
...

143重排链表

题目描述:
给定一个单链表 L:L0→L1→…→Ln-1→Ln ,将其重新排列后变为: L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
输入示例:
5
1 2 3 4 5
输出示例:
head–>1–>5–>2–>4–>3–>tail

思路:看了题解
1.找中间位置,快慢指针思想吧,p走一步q走两步,当q走到链表末尾的时候p恰好在中间位置。
2.逆置后半部分链表(实质上用的是头插法逆置)
3.将逆置后的尾部依次插入前半部分链表(直白写法)
代码:

#include<iostream>
using namespace std;
  struct ListNode {
      int val;
      ListNode *next;
      ListNode() : val(0), next(nullptr) {} 
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
  };

 ListNode *createByTail()
 {    
         ListNode *head;    
	 ListNode *p1,*p2;    
	 int n=0,num;    
	 int len;    
	 cin>>len;    
	 head=NULL;    
	 while(n<len && cin>>num)    
	 {        
		 p1=new ListNode(num);        
		 n=n+1;        
		 if(n==1)            
		 head=p1;        
		 else            
		 p2->next=p1;        
		 p2=p1;    	
	}    
	 return head;
}
void  displayLink(ListNode *head)
{    
	ListNode *p;    
	p=head;    
	cout<<"head-->";    
	while(p!= NULL)    
	{        
		cout<<p->val<<"-->";        
		p=p->next;    
	}    
	cout<<"tail\n";
}
class Solution {
public:
    void reorderList(ListNode* head) {
        ListNode *p=head,*q=head,*r;
        if(!head)
        return ;
        while(q->next)//找中间结点
        {
            p=p->next;
            q=q->next;
            if(q->next)
             q=q->next;
        }
        q=p->next;
        p->next=nullptr;
        while(q)//逆置后半部分
        {
            r=q->next;
            q->next=p->next;
            p->next=q;
            q=r;
        }
        q=p->next;
        p->next=nullptr;
        p=head;
        while(q)//将逆置后的后半部分链表插入到前边
        {
            r=q->next;
            q->next=p->next;
            p->next=q;
            p=q->next;
            q=r;
        }
    }
};
int main()
{    
	ListNode* head = createByTail();    
	Solution().reorderList(head);    
	displayLink(head);    
	return 0;
}

DHU给了输入输出代码 存一下。
小坑:写第一个p->next=null的时候晕了,写成p=null…一直报错 无语了 细心点。