上一篇博客中，我们通过几道简单的例题，对链表的知识有所巩固，本篇文章将继续讲解例题，欢迎观看~
1.将两个有序链表合并为一个新的有序链表并返回。
注意：新链表是通过拼接给定的两个链表的所有节点组成的。
我们还是借助图来理解
如图，就是将两个有序链表合为一个有序链表
1.申请一个newHead节点，让两个链表的头节点进行比较，谁小谁就是新链表的头节点
2.定义一个TH节点，让TH也指向newHead节点
3定义循环，两个head都不为空
4，使用if,如果链表1大于链表2
th.next =b;
th = th.next;
b = b.next
else
th.next = a;
th = th.next;
a= a.next
5.判断headA和headB是否为空 ，如果headA为空，全都串headB即可，如果headB为空，剩下全串headA即可
温馨提示：请借助上方图片进行理解
代码如下
public static MySingleList.ListNode mergeTowList(MySingleList.ListNode headA, MySingleList.ListNode headB){
MySingleList.ListNode newHead = new MySingleList.ListNode();//这里不要忘记创建构造方法
MySingleList.ListNode tmpHead = newHead;
while (headA != null&&headB != null){
if (headA.val>headB.val){
tmpHead.next = headB;
headB = headB.next;
}else {
tmpHead.next = headA;
headA= headA.next;
}
tmpHead = tmpHead.next;
}
if (headA == null){
tmpHead.next = headB;
}
if (headB==null){
tmpHead.next= headA;
}
return newHead.next;
}
调用测试
public static void main(String[] args) {
MySingleList mySingleList = new MySingleList();
mySingleList.addLast(1);
mySingleList.addLast(4);
mySingleList.addLast(7);
mySingleList.addLast(8);
mySingleList.addLast(12);
mySingleList.display();
MySingleList mySingleList1= new MySingleList();
mySingleList1.addLast(2);
mySingleList1.addLast(5);
mySingleList1.addLast(6);
mySingleList1.addLast(38);
mySingleList1.addLast(47);
mySingleList1.display();
MySingleList.ListNode nh = mergeTowList(mySingleList.head,mySingleList1.head);
mySingleList.display(nh);
}
运行截图
2.编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
注意：给定值，不一定是链表中的数据，并且保证原来顺序不变
如图
1.分为两部分，分别定义第一部分开始（bs）结束（be），第二部分的开始（as）结束（ae）
为保证原来顺序不变，建议使用尾插法
如图
2.可能会出现死循环，我们借图理解
此时，如果最大的数据不是最后一个，就会出现死循环，所以我们要手动置null
还有一i些细节
1.第一次插入bs，be都要指向node
be.next = 0x98
代码如下
public ListNode partition(ListNode pHead, int x) {
// write code here
ListNode bs = null;
ListNode be = null;
ListNode as = null;
ListNode ae = null;
ListNode cur = pHead;
//没有遍历完 整个链表
while(cur != null) {
if(cur.val < x) {
//第一次插入
if(bs == null) {
bs = be = cur;
}else {
be.next = cur;
be = be.next;
}
}else {
//第一次插入
if(as == null) {
as = ae = cur;
}else {
ae.next = cur;
ae = ae.next;
}
}
cur = cur.next;
}
//第一个段 没有数据
if(bs == null) {
return as;
}
be.next = as;
//防止 最大的数据 不是最后一个
if(as!=null) {
ae.next = null;
}
return bs;
}
3.链表的回文结构
什么是回文结构呢，我们还是借助图来理解
此时链表为单向结构，并且我们硬性要求不能申请一个数组，将数据放入数组，判断数组是否是回文
思路：将后半部分链表反转即可 如图
1.找到链表中间节点（快慢指针，此方法上篇文章中有详细讲解，这里不多做赘述）
2.反转中间节点之后的 的节点（定义一个cur 让cur等于slow后面的节点，定义一个curNext保存cur后面的节点，循环条件为cur！=null）
curNext = cur.next:cur.next = slow:
让slow和cur都向后走
slow = chur:cur = curNext
如图
3.从前向后开始比较、（head向后走slow向前走，没有相遇，值不一样返回false，循环条件为head！=slow）
注意：偶数时head.next = slow返回true如图
代代码如下
public boolean chkPalindrome() {
// 1. 找到中间位置
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//2. 开始翻转
ListNode cur = slow.next;
while(cur != null) {
ListNode curNext = cur.next;//记录一下下一个节点
cur.next = slow;
slow = cur;
cur = curNext;
}
//3. 此时翻转完成，开始判断是否回文
while(head != slow) {
if(head.val != slow.val) {
return false;
}
if(head.next == slow) {
return true;
}
head = head.next;
slow = slow.next;
}
return true;
}
调调用测试
public static void main(String[] args) {
MySingleList mySingleList = new MySingleList();
mySingleList.createList();
mySingleList.display();
boolean ret = mySingleList.chkPalindrome();
System.out.println(ret);
}
运运行结果
到
此为止，本篇文章就到此结束啦，本篇文章中我们主要介绍了 将两个有序链表合并为一个新的有序链表并返回，编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前，链表的回文结构三种方法，下一篇文章中我们将继续讲解例题，敬请期待叭~
参考文章
发表评论