【Java--数据结构】链表经典OJ题详解（下）

前言

上一篇

欢迎关注个人主页：逸狼

---

创造不易，可以点点赞吗~

如有错误，欢迎指出~

---

---

目录

前言

链表分割 

链表的回文结构

 相交链表

环形链表

---

链表分割 

编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。OJ链接

1.定义一个节点cur遍历原链表,创建两个新链表B和A，用于放小于x和大于x的，最后将这两个链表连接构成一个新链表。这两个链表分别创建两个节点bs be和as ae,bs作为B链表的头节点,be用于添加节点，as和ae同理

2.比较每个节点的val与x的大小

若valx，则该节点放在新链表A中

• ae.next=cur;
• ae=ae.next;

  其中要注意第一次插入ae=as=cur;

  3.注意：

  最后一个节点的next，没有null

  要判断全部小于x，或全部大于等于x的情况（即遍历完原链表发现B链表为空或者A链表为空）

  发现B链表为空 直接返回A链表 return as;

  4.拼接

  将B和A链表拼接，return bs;

  

  

  public class Partition {
      public ListNode partition(ListNode pHead, int x) {
          if(pHead==null){
              return null;
          }
          // write code here
          ListNode bs=null;
          ListNode be=null;
          ListNode as=null;
          ListNode ae=null;
          ListNode cur=pHead;
          while(cur!=null){
              if(cur.val