【数据结构_6上篇】有关链表的oj题

import java.util.*;/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Partition {public ListNode partition(ListNode pHead, int x) {// write code here//1.首先要判断链表是否为空的情况if(pHead == null){return pHead;}//2.来解决一般情况//创建两个新的链表 一个用来记录比x值大的元素 一个用来记录比x值小的元素//因为后期涉及到尾插操作，我们再分别为这两个新的链表设置一个尾巴//为了使后期的插入操作变得简单，我们为两个链表都创建傀儡节点ListNode largeNode =  new ListNode(0);ListNode largeTail = largeNode;ListNode smallNode = new ListNode(0);ListNode smallTail = smallNode;//接下来我们进行链表的遍历操作ListNode cur = pHead;for(;cur != null; cur = cur.next){if(cur.val >= x ){//如果比x大 那就放进largetaillargeTail.next = cur;largeTail = cur;}else{//如果比x小 那就放进smalltailsmallTail.next = cur;smallTail = cur;}}//此时两个链表都书写完毕 接下来就要将他们两个进行相连smallTail.next = largeNode.next;largeTail.next = null;return smallNode.next;}
}

空间复杂度为O（N）的解法

import java.util.*;/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class PalindromeList {public boolean chkPalindrome(ListNode A) {// write code here//0.首先考虑特殊情况//0.1 如果链表为空 那么直接返回if(A == null){return true;}//0.2 如果链表中只有一个元素 那么也直接返回if(A.next == null){return true;}//1.首先我们先复制一个与A一摸一样的链表ListNode newHead = new ListNode(0);ListNode newTail = newHead;ListNode cur1 = A;for(;cur1!=null;cur1 = cur1.next){//*不是直接将A中的节点赋值，而是要另外复制一份ListNode node = new ListNode(cur1.val);newTail.next = node;newTail = node;}//不再使用傀儡节点newHead = newHead.next;//2.完成了复制之后 我们要将新的链表进行逆置ListNode prev = null;ListNode cur = newHead;while(cur!= null){//每次循环开始前都要创建一个nextListNode next = cur.next;if(next == null){//说明结束了，此时的cur为新的头节点newHead = cur;}cur.next = prev;prev = cur;cur = next;}//3.对A与逆置的链表进行比较ListNode cur3 = A;ListNode cur4 = newHead;while(cur3 != null && cur4 != null){if(cur3.val != cur4.val){return false;}cur3 = cur3.next;cur4 = cur4.next;}//4.出来后还要比较二者的长度if(cur3 == null && cur4 == null){return true;}return false;}
}

空间复杂度为O（1）的写法

import java.util.*;/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class PalindromeList {public boolean chkPalindrome(ListNode A) {// write code hereif (A == null) {return true;}if (A.next == null) {return true;}// 1. 找到链表中间节点.int size = size(A);int step = size / 2;ListNode B = A;for (int i = 0; i < step; i++) {B = B.next;}// 此时 B 指向的就是中间节点了.// 2. 针对 B 这个链表进行逆置.ListNode prev = null;ListNode cur = B;while (cur != null) {ListNode next = cur.next;if (next == null) {// cur 就是新的头节点.B = cur;}cur.next = prev;prev = cur;cur = next;}// 3. 比较 A 和 B 两个链表是否相同.ListNode cur1 = A;ListNode cur2 = B;while (cur1 != null && cur2 != null) {if (cur1.val != cur2.val) {return false;}cur1 = cur1.next;cur2 = cur2.next;}// 不去考虑长度问题了. 如果节点是偶数个, 此时 A 的长度就是会比 B 多一个.return true;}public int size(ListNode head) {int size = 0;for (ListNode cur = head; cur != null; cur = cur.next) {size++;}return size;}
}