反转单向链表
思路
使用一个临时节点当做缓冲节点,通过绕圈完成反转
image.png
public class _链表反转 {
public static void main(String[] args) {
ListNode listNode = LinkListCommon.genLinkList(5);
System.out.println("反转前");
LinkListCommon.printLinKList(listNode);
ListNode newNode=reverse(listNode);
System.out.println("反转后");
LinkListCommon.printLinKList(newNode);
}
private static ListNode reverse(ListNode head) {
ListNode newHead=null;
while(head!=null){
ListNode tmp=head.next;
head.next=newHead;
newHead=head;
head=tmp;
}
return newHead;
}
}
反转部分链表
题:给定一个链表,及反转的范围,完成反转
思路
可参考反转链表
image.png
public class _反转部分链表 {
public static void main(String[] args) {
ListNode listNode = LinkListCommon.genLinkList(10);
System.out.println("反转前");
LinkListCommon.printLinKList(listNode);
ListNode newNode = reverseBetween(listNode, 3, 8);
System.out.println("反转后");
LinkListCommon.printLinKList(newNode);
}
private static ListNode reverseBetween(ListNode head, int m, int n) {
//备份头节点和m的前驱节点
ListNode initHead = head;
ListNode pre = null;
for (int i = 1; i < m; i++) {
pre = head;
head = head.next;
}
//System.out.println("m节点为>"+head.val+">前驱节点为>>"+pre.val);
//反转[m,n]部分的链表
ListNode newHead = null;
for (int i = m; i <= n; i++) {
ListNode tmp = head.next;
head.next = newHead;
newHead = head;
head = tmp;
//System.out.println("新head>>" + head);
}
//将
if (pre != null) {
pre.next.next = head;
pre.next = newHead;
} else {
//表示从链表的第一个就进行反转
initHead.next.next = head;
initHead.next = newHead;
}
return initHead;
}
}
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
@Override
public String toString() {
return val + " -> " + next;
}
}
移除链表
/**
* https://leetcode-cn.com/problems/remove-linked-list-elements/
*
* @author MJ
*
*/
public class _0203_移除链表元素 {
// public ListNode removeElements(ListNode head, int val) {
// if (head == null) return null;
//
// // 新链表的头结点
// ListNode newHead = null;
// // 新链表的尾结点
// ListNode newTail = null;
//
// while (head != null) {
// if (head.val != val) {
// // 将head拼接到newTail的后面
// if (newTail == null) {
// newHead = head;
// newTail = head;
// } else {
// newTail.next = head;
// newTail = head;
// }
// }
// head = head.next;
// }
// if (newTail == null) {
// return null;
// } else {
// // 尾结点的next要清空
// newTail.next = null;
// }
// return newHead;
// }
public ListNode removeElements(ListNode head, int val) {
if (head == null) return null;
// 新链表的头结点
ListNode newHead = new ListNode(0);
// 新链表的尾结点
ListNode newTail = newHead;
while (head != null) {
if (head.val != val) {
newTail.next = head;
newTail = head;
}
head = head.next;
}
newTail.next = null;
return newHead.next;
}
}
相加链表
package 链表;
/**
* https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
*
* @author MJ
*
*/
public class _0160_相交链表 {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode curA = headA, curB = headB;
while (curA != curB) {
curA = (curA == null) ? headB : curA.next;
curB = (curB == null) ? headA : curB.next;
// 这段代码在两个链表不相交的时候会死循环
// curA = (curA.next == null) ? headB : curA.next;
// curB = (curB.next == null) ? headA : curB.next;
}
return curA;
}
}
分割链表
package 链表;
/**
* https://leetcode-cn.com/problems/partition-list/
*
* @author MJ
*
*/
public class _0086_分隔链表 {
public ListNode partition(ListNode head, int x) {
if (head == null) return null;
ListNode lHead = new ListNode(0);
ListNode lTail = lHead;
ListNode rHead = new ListNode(0);
ListNode rTail = rHead;
while (head != null) {
if (head.val < x) { // 放在lTail后面
lTail.next = head;
lTail = head;
} else { // 放在rTail后面
rTail.next = head;
rTail = head;
}
head = head.next;
}
// 这句代码不能少
/*
* 因为可能出现这样的情况:
* 原链表倒数第N个节点A的值是>=x的，A后面所有节点的值都是<x的
* 然后rTail.next最终其实就是A.next
*/
rTail.next = null;
// 将rHead.next拼接在lTail后面
lTail.next = rHead.next;
return lHead.next;
}
}
两数相加
package 链表;
/**
* https://leetcode-cn.com/problems/add-two-numbers/
*
* @author MJ
*
*/
public class _0002_两数相加 {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode dummyHead = new ListNode(0);
ListNode last = dummyHead;
// 进位值
int carry = 0;
while (l1 != null || l2 != null) {
int v1 = 0;
if (l1 != null) {
v1 = l1.val;
l1 = l1.next;
}
int v2 = 0;
if (l2 != null) {
v2 = l2.val;
l2 = l2.next;
}
int sum = v1 + v2 + carry;
// 设置进位值
carry = sum / 10;
// sum的个位数作为新节点的值
last.next = new ListNode(sum % 10);
last = last.next;
}
// 检查最后的进位
if (carry > 0) {
// carry == 1
last.next = new ListNode(carry);
}
return dummyHead.next;
}
}
网友评论