public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
/**
考虑构建两个节点指针 A? , B 分别指向两链表头节点 headA , headB ，做如下操作：
指针 A 先遍历完链表 headA ，再开始遍历链表 headB ，当走到 node 时，共走步数为：a + (b - c)
指针 B 先遍历完链表 headB ，再开始遍历链表 headA ，当走到 node 时，共走步数为：b + (a - c)
如下式所示，此时指针 A , B 重合，并有两种情况：
a + (b - c) = b + (a - c)
*/
ListNode a = headA,b=headB;
while(a!=b){
if(a!=null){a=a.next;}
else{a=headB;}
if(b!=null){
b=b.next;
}else{b=headA;}
}
return a;
}
}?
class Solution {
public ListNode reverseList(ListNode head) {
ListNode cur = head;
ListNode pre = null;
ListNode tmp = null;
// 定义两个指针并且定义一个中间的临时指针
while(cur != null){
tmp = cur.next;
cur.next= pre;
pre = cur;
cur =tmp;
}
return pre;
}
}
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head ==null || head.next == null) return head;
ListNode res = head;
// 原地断链，并指向下一个
while(head.next != null){
if(head.val == head.next.val){
head.next = head.next.next;
}else{
head = head.next;
}
}
return res;
}
}
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
/**
利用快慢指针的方法，先让两个指针之间的距离为n，然后同步向末尾走，这样第一个指针走到尾的时候，第二个指针刚好在倒数第n的位置，只有一个节点的情况要单独分析，同时还需要考虑删除头结点的情况，因此，在head的前面加上一个节点
*/
if(head.next ==null && n ==1) return null;
ListNode first = new ListNode(0);
first.next = head;
ListNode pre = first;
ListNode ne = first;
int p=0,q=0;
while(pre.next !=null){
if(p-q <n){
pre = pre.next;
p++;
}
else if(p-q == n){
pre= pre.next;
ne = ne.next;
p++;q++;
}
}
ne.next = ne.next.next;
return first.next;
}
}
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
public ListNode swapPairs(ListNode head) {
/**
需要四个指针；当前节点、当前节点的前序节点、当前节点的后续节点，当前节点后续节点的后续
*/
ListNode node = new ListNode(-1); // 定义一个前序节点
node.next = head;
ListNode pre = node;
// 需要当前节点的后面两个节点都不是空，才能进行交换
while(pre.next != null && pre.next.next != null){
ListNode l1 = pre.next,l2=pre.next.next;
ListNode next = l2.next; //这样就定义了四个指针 pre 、l1、l2、next
// 开始断链交换
l1.next = next;
l2.next = l1;
pre.next = l2;
// pre移动到l1的位置，开启下一轮的两两交换
pre = l1;
}?
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
/**
由于栈是先进后出的，因此可以将链表加入到一个栈中，这样最先出来的数就是链表的最后一个，也就是各位
*/
Stack<Integer> l1Stack = buildStack(l1);
Stack<Integer> l2Stack = buildStack(l2);
ListNode head = new ListNode(-1);
int carry = 0; // 存储后面加法运算的累加和
while(!l1Stack.isEmpty() || !l2Stack.isEmpty() || carry!=0){
int x = l1Stack.isEmpty() ? 0: l1Stack.pop();
int y = l2Stack.isEmpty() ? 0: l2Stack.pop();
int sum = x+y+carry;
// 创建一个临时节点取存储和的个位数
ListNode node = new ListNode(sum %10);
//头插法，从末尾往前面插入
node.next = head.next;
head.next = node;
carry = sum/10;
}
return head.next;
}
// 封装一个入栈的方法
private Stack<Integer> buildStack(ListNode l){
Stack<Integer> tempStack = new Stack();
while(l!=null){
tempStack.push(l.val);
l= l.next;
}
retrun tempStack;
}?
class Solution {
public boolean isPalindrome(ListNode head) {
/**
把当前链表切成两段，然后把后半段反转，最后比较两段是否相等
利用快慢指针的方法；快指针一次走两步，慢指针一次走一步
*/
if(head ==null || head.next==null) return true;
ListNode fast = head.next,slow = head;
// 因为链表为偶数或者奇数的时候，快指针可能落在最后一个节点或者最后的下一个空位置，因此要用逻辑与判断
while(fast !=null && fast.next != null){
/**
用两倍的方法走，长度为偶数时，快指针走到尾，慢指针在一半的位置，为奇数的时候，慢指针在一半加一的位置。
*/
slow = slow.next;
fast = fast.next.next;
}
// 用head 和slow 表示分割后的两个链表的头结点,因此如果链表长度是偶数的时候，slow需要后移一位
if(fast != null){
slow = slow.next;
}
// 切割
cut(head,slow);
// 反转比较
return isEqual(head,reverse(slow));
}
// 切割
private void cut(ListNode l1,ListNode l2){
while(l1.next != l2){
l1 = l1.next;
}
l1.next = null;
}
// 反转
private ListNode reverse(ListNode head){
ListNode pre = null;
while(head != null){
ListNode tmp = head.next;
head.next = pre;
pre = head;
head = tmp;
}
return pre;
}
// 比较是否相等
private boolean isEqual(ListNode l1,ListNode l2){
while(l1 != null && l2 != null){
if(l1.val != l2.val){
return false;
}
l1=l1.next;
l2 = l2.next;
}
return true;
}
}?
class Solution {
public ListNode[] splitListToParts(ListNode head, int k) {
int N = 0;
ListNode cur = head;
// 计算长度
while(cur != null){
N++;
cur = cur.next;
}
// 如果能等分，计算出等分后剩余的后部节点
int mod = N%k;
// 恰好可以等分，计算每一份的长度
int size = N/k;
// 定义结果集，存储链表的数组
ListNode[] result = new ListNode[k];
// 开始计算，让指针回到头节点
cur = head;
// 外层循环是将等分后不为空的链表装入数组中对应下标位置中
for(int i =0;cur != null && i<k;++i){
result[i] = cur; // 把头结点装入，此时只装了头节点，后面再装入后续节点
// 如果mod余数不是0，需要将其分配给前mod个节点，每个多一个
int curSize = size +(mod-- >0 ? 1:0); // mod每次减一，大于0则size要加一
for(int j =0;j<curSize-1;++j){ // 在头节点之后拼接其他的节点
cur = cur.next; // 因为这里到了下一个，所以cursize需要-1
}
// 拼接一段之后进行断链
ListNode next = cur.next;
cur.next = null;
cur = next;
}
return result;
}
}
?
class Solution {
public ListNode oddEvenList(ListNode head) {
// 编号区分奇数偶数
if(head == null) return head;
ListNode odd = head,even = head.next,evenHead = even;
while(even != null && even.next != null){
odd.next = odd.next.next; // 拼接奇数节点
odd = odd.next;
// 凭借偶数节点
even.next = even.next.next;
even = even.next
}
// 将奇偶两段拼接起来
odd.next = evenHead;
return head;
}
}?