- LeetCode 160.相交链表
编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表：
在节点 c1 开始相交。
示例 1：
示例1
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
注意：
如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
//令两个指针分别指向两个链表的头，然后依次往后遍历，当一个链表遍历至尾时，令指针指向另一链表的头。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode l1 = headA;
ListNode l2 = headB;
while(l1 != l2){
l1 = (l1 == null) ? headB : l1.next;
l2 = (l2 == null) ? headA : l2.next;
}
return l1;
}
}
- LeetCode 21.合并两个有序链表
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
/**
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode result = new ListNode(0);//创建一个新链表用于保存合并后的结果
ListNode curr = result;//创建一个指向结果链表头结点的指针，用于执行归并操作
while(l1 != null && l2 != null){ //如果l1和l2都还有元素
if(l1.val < l2.val){ //如果l1元素较小，插入结果链表，两个链表都进行后移
curr.next = l1;
curr = curr.next;
l1 = l1.next;
}else{
curr.next = l2;
curr = curr.next;
l2 = l2.next;
}
}
if(l1 == null){
curr.next = l2; //如果l2已经无元素，则插入l1剩余元素
}else{
curr.next = l1;
}
return result.next;
}
}
- LeetCode 328.奇偶链表
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
示例 1:
输入:1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
示例 2:
输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL
说明:
应当保持奇数节点和偶数节点的相对顺序。
链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode oddEvenList(ListNode head) {
if(head == null){
return head;
}
ListNode odd = head; //奇指针指向链表头
ListNode even = head.next; //偶指针指向链表头指向的下一个元素(第一个偶数对象)
ListNode 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;
}
}
- LeetCode 206.反转链表
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null||head.next == null){
return head;
}
ListNode p = head;
ListNode newH = null;
while(p!=null){
ListNode temp = p.next;
p.next = newH;
newH = p;
p = temp;
}
return newH;
}
}
- LeetCode 19.删除链表中的倒数第N个节点
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast_p = dummy;
ListNode slow_p = dummy;
for(int i = 0; i < n + 1; i++){
fast_p = fast_p.next;
}
while(fast_p != null){
fast_p = fast_p.next;
slow_p = slow_p.next;
}
slow_p.next = slow_p.next.next;
return dummy.next;
}
}
- LeetCode 445.两数相加②
给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶:
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例:
输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 8 -> 0 -> 7
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> l1_Stack = LinkListToStack(l1);
Stack<Integer> l2_Stack = LinkListToStack(l2);
int carry = 0;
ListNode head = new ListNode(-1);
while(!l1_Stack.isEmpty() || !l2_Stack.isEmpty() || carry != 0){
int l1_val = l1_Stack.isEmpty() ? 0 : l1_Stack.pop();
int l2_val = l2_Stack.isEmpty() ? 0 : l2_Stack.pop();
int sum = l1_val + l2_val + carry;
ListNode node = new ListNode(sum % 10);
node.next = head.next;
head.next = node;
carry = sum / 10;
}
return head.next;
}
private Stack<Integer> LinkListToStack(ListNode l) {
Stack<Integer> stack = new Stack<>();
while(l != null){
stack.push(l.val);
l = l.next;
}
return stack;
}
}
- LeetCode 2.两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode result = new ListNode(0);
ListNode temp = result;
int sum = 0;
while(l1!=null || l2!= null){
if(l1!= null){
sum += l1.val;
l1 = l1.next;
}
if(l2!= null){
sum += l2.val;
l2 = l2.next;
}
temp.next = new ListNode(sum % 10);
temp = temp.next;
sum = sum / 10;
}
if(sum != 0){
temp.next = new ListNode(1);
}
return result.next;
}
}
- LeetCode 234.回文链表
请判断一个链表是否为回文链表。
示例 1:
输入:1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
//使用快慢指针找到链表的中段。
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null){
return true;
}
ListNode slow_p = head;
ListNode fast_p = head.next;
while(fast_p != null && fast_p.next != null){
slow_p = slow_p.next;
fast_p = fast_p.next.next;
}
if(fast_p != null){
slow_p = slow_p.next;
}
cut(head,slow_p);
return isEqual(head,reverse(slow_p));
}
//剪切链表让其划分为两段
private void cut(ListNode head,ListNode cutNode){
while(head.next != cutNode){
head = head.next;
}
head.next = null;
}
//翻转链表
private ListNode reverse(ListNode head){
ListNode newH = null;
while(head != null){
ListNode temp = head.next;
head.next = newH;
newH = head;
head = temp;
}
return newH;
}
//判断链表是否回文
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;
}
}
- LeetCode 83.删除排序链表中的重复元素
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入: 1->1->2
输出: 1->2
示例 2:
输入: 1->1->2->3->3
输出: 1->2->3
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode current = head;
while(current != null && current.next != null){
if(current.val == current.next.val){
current.next = current.next.next;
}else{
current = current.next;
}
}
return head;
}
}
- LeetCode 19.删除链表的倒数第N个节点
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明:
给定的 n 保证是有效的。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast_p = dummy;
ListNode slow_p = dummy;
for(int i = 0; i < n + 1; i++){
fast_p = fast_p.next;
}
while(fast_p != null){
fast_p = fast_p.next;
slow_p = slow_p.next;
}
slow_p.next = slow_p.next.next;
return dummy.next;
}
}
