反转链表
package 复现代码;
import org.junit.Test;
/**
* @Classname 反转链表II
* @Description TODO
* @Date 2020/12/21 12:56
* @Created by xjl
*/
public class 反转链表II {
public class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public ListNode rever(ListNode head) {
if (head == null) {
return null;
}
ListNode pre = null;
ListNode curr = head;
while (curr != null) {
ListNode future = curr.next;
curr.next = pre;
pre = curr;
curr = future;
}
return pre;
}
public ListNode rever1(ListNode head) {
if (head == null) {
return null;
}
ListNode dumy = new ListNode(0);
dumy.next = head;
ListNode pre = dumy;
ListNode curr = head;
while (curr.next != null) {
ListNode future = curr.next;
curr.next = future.next;
future.next = dumy.next;
pre.next = future;
}
return dumy.next;
}
@Test
public void test() {
ListNode s1 = new ListNode(1);
ListNode s2 = new ListNode(2);
ListNode s3 = new ListNode(3);
ListNode s4 = new ListNode(4);
ListNode s5 = new ListNode(5);
s1.next = s2;
s2.next = s3;
s3.next = s4;
s4.next = s5;
ListNode res = rever1(s1);
while (res != null) {
System.out.print(res.val + " ");
res = res.next;
}
}
}
package 复现代码;
/**
* @Classname 判断链表时候有环
* @Description TODO
* @Date 2020/12/21 14:38
* @Created by xjl
*/
public class 判断链表时候有环 {
public class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public boolean cycle(ListNode head) {
if (head == null) {
return false;
}
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast=fast.next.next;
slow=slow.next;
if (fast==slow){
return true;
}
}
return false;
}
}
package 复现代码;
/**
* @Classname 判断环的入口
* @Description TODO
* @Date 2020/12/21 14:44
* @Created by xjl
*/
public class 判断环的入口 {
public class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public ListNode test(ListNode head) {
if (head == null) {
return null;
}
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (slow == fast) {
//表示有环
ListNode start = head;
ListNode end = slow;
while (start != end) {
start = start.next;
end = end.next;
}
return start;
}
}
return null;
}
}package 复现代码;
/**
* @Classname 合并链表
* @Description TODO
* @Date 2020/12/21 14:53
* @Created by xjl
*/
public class 合并链表 {
public class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
/**
* @description TODO 链表的都是有序的
* @param: head1
* @param: head2
* @date: 2020/12/21 14:58
* @return: 复现代码.合并链表.ListNode
* @author: xjl
*/
public ListNode merge(ListNode head1, ListNode head2) {
if (head1 == null && head2 != null) {
return head2;
}
if (head1 != null && head2 == null) {
return head1;
}
if (head1 == null && head2 == null) {
return null;
}
ListNode dumpy=new ListNode(0);
ListNode curr=dumpy;
ListNode curr1 = head1;
ListNode curr2 = head2;
while (curr1 != null && curr2 != null) {
if (curr1.val>=curr2.val){
curr.next=curr2;
curr2=curr2.next;
}else {
curr.next=curr1;
curr1=curr1.next;
}
curr=curr.next;
}
while (curr1!=null){
curr.next=curr1;
curr=curr.next;
curr1=curr.next;
}
while (curr2!=null){
curr.next=curr2;
curr=curr.next;
curr2=curr.next;
}
return dumpy.next;
}
}package 复现代码;
import org.junit.Test;
/**
* @Classname 删除链表的重复元素
* @Description TODO
* @Date 2020/12/21 15:06
* @Created by xjl
*/
public class 删除链表的重复元素 {
public class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public ListNode delete(ListNode head) {
if (head == null) {
return head;
}
ListNode curr = head;
while (curr.next != null) {
if (curr.val == curr.next.val) {
curr.next = curr.next.next;
} else {
curr = curr.next;
}
}
return head;
}
public ListNode de(ListNode head) {
if (head == null) {
return null;
}
ListNode curr = head;
while (curr != null && curr.next != null) {
ListNode future = curr.next;
if (future.val == curr.val) {
curr.next = future.next;
}else {
curr = curr.next;
}
}
return head;
}
@Test
public void test() {
ListNode s1 = new ListNode(1);
ListNode s2 = new ListNode(1);
ListNode s3 = new ListNode(2);
ListNode s4 = new ListNode(3);
ListNode s5 = new ListNode(3);
s1.next = s2;
s2.next = s3;
s3.next = s4;
s4.next = s5;
ListNode res = delete(s1);
while (res != null) {
System.out.print(res.val + " ");
res = res.next;
}
}
}
package 名企高频面试题143;
import org.junit.Test;
/**
* @Classname 链表删除所有重复元素
* @Description TODO
* @Date 2020/12/18 10:03
* @Created by xjl
*/
public class 链表删除所有重复元素 {
/**
* @description TODO 删除的是的链表的重复的元素
* @param: head
* @date: 2020/12/18 10:04
* @return: ListNode
* @author: xjl
*/
public ListNode deleteDuplicates(ListNode head) {
if (head == null){
return null;
}
ListNode dumy = new ListNode(0);
dumy.next = head;
ListNode pre = dumy;
ListNode curr = head;
while (curr != null && curr.next != null) {
ListNode future = curr.next;
if (future.val != curr.val) {
pre = pre.next;
curr = curr.next;
} else {
while (future != null && future.val == curr.val) {
future = future.next;
}
pre.next = future;
curr = future;
}
}
return dumy.next;
}
public ListNode deleteDuplicates2(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy;
ListNode curr = head;
while (curr != null && curr.next != null) {
if (curr.val == curr.next.val) {
ListNode future = curr.next;
while (future != null && future.val == curr.val) {
future = future.next;
}
prev.next = future;
curr = future;
} else {
prev = prev.next;
curr = curr.next;
}
}
return dummy.next;
}
@Test
public void test() {
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(1);
ListNode node3 = new ListNode(1);
ListNode node4 = new ListNode(1);
ListNode node5 = new ListNode(1);
ListNode node6 = new ListNode(4);
ListNode node7 = new ListNode(5);
ListNode node8 = new ListNode(6);
node1.next = node2;
node2.next = node3;
// node3.next = node4;
// node4.next = node5;
// node5.next = node6;
// node6.next = node7;
// node7.next = node8;
ListNode res = deleteDuplicates(node1);
while (res != null) {
System.out.print(res.val + " ");
res = res.next;
}
}
public class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
}
