- LeetCode 160.相交鏈表
編寫一個程序桨菜，找到兩個單鏈表相交的起始節(jié)點吮成。
如下面的兩個鏈表：
在節(jié)點 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
輸入解釋：相交節(jié)點的值為 8 （注意蒜田，如果兩個列表相交則不能為 0）。從各自的表頭開始算起膜廊，鏈表 A 為 [4,1,8,4,5]乏沸，鏈表 B 為 [5,0,1,8,4,5]。在 A 中爪瓜，相交節(jié)點前有 2 個節(jié)點蹬跃；在 B 中，相交節(jié)點前有 3 個節(jié)點铆铆。
注意：
如果兩個鏈表沒有交點炬转，返回 null.
在返回結果后，兩個鏈表仍須保持原有的結構算灸。
可假定整個鏈表結構中沒有循環(huán)。
程序盡量滿足 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.合并兩個有序鏈表
將兩個有序鏈表合并為一個新的有序鏈表并返回贼涩。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的巧涧。
示例：
輸入：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);//創(chuàng)建一個新鏈表用于保存合并后的結果
ListNode curr = result;//創(chuàng)建一個指向結果鏈表頭結點的指針，用于執(zhí)行歸并操作
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.奇偶鏈表
給定一個單鏈表袒哥，把所有的奇數(shù)節(jié)點和偶數(shù)節(jié)點分別排在一起缩筛。請注意，這里的奇數(shù)節(jié)點和偶數(shù)節(jié)點指的是節(jié)點編號的奇偶性堡称，而不是節(jié)點的值的奇偶性瞎抛。
請嘗試使用原地算法完成。你的算法的空間復雜度應為 O(1)却紧，時間復雜度應為 O(nodes)桐臊，nodes 為節(jié)點總數(shù)。
示例 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
說明:
應當保持奇數(shù)節(jié)點和偶數(shù)節(jié)點的相對順序晓殊。
鏈表的第一個節(jié)點視為奇數(shù)節(jié)點断凶，第二個節(jié)點視為偶數(shù)節(jié)點，以此類推巫俺。
/**
* 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; //偶指針指向鏈表頭指向的下一個元素(第一個偶數(shù)對象)
ListNode evenHead = even; //保存對應的偶數(shù)節(jié)點
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.刪除鏈表中的倒數(shù)第N個節(jié)點
給定一個鏈表砚著，刪除鏈表的倒數(shù)第 n 個節(jié)點次伶，并且返回鏈表的頭結點。
示例：
給定一個鏈表: 1->2->3->4->5, 和 n = 2.
當刪除了倒數(shù)第二個節(jié)點后稽穆，鏈表變?yōu)?1->2->3->5.
說明：
給定的 n 保證是有效的冠王。
進階：
你能嘗試使用一趟掃描實現(xià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.兩數(shù)相加②
給定兩個非空鏈表來代表兩個非負整數(shù)舌镶。數(shù)字最高位位于鏈表開始位置柱彻。它們的每個節(jié)點只存儲單個數(shù)字。將這兩數(shù)相加會返回一個新的鏈表餐胀。
你可以假設除了數(shù)字 0 之外哟楷，這兩個數(shù)字都不會以零開頭。
進階:
如果輸入鏈表不能修改該如何處理否灾？換句話說卖擅，你不能對列表中的節(jié)點進行翻轉。
示例:
輸入: (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.兩數(shù)相加
給出兩個 非空 的鏈表用來表示兩個非負的整數(shù)墨技。其中惩阶，它們各自的位數(shù)是按照 逆序 的方式存儲的，并且它們的每個節(jié)點只能存儲 一位 數(shù)字扣汪。
如果断楷，我們將這兩個數(shù)相加起來，則會返回一個新的鏈表來表示它們的和崭别。
您可以假設除了數(shù)字 0 之外冬筒，這兩個數(shù)都不會以 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.刪除排序鏈表中的重復元素
給定一個排序鏈表暗膜，刪除所有重復的元素匀奏，使得每個元素只出現(xiàn)一次。
示例 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.刪除鏈表的倒數(shù)第N個節(jié)點
給定一個鏈表学搜，刪除鏈表的倒數(shù)第 n 個節(jié)點娃善，并且返回鏈表的頭結點。
示例：
給定一個鏈表: 1->2->3->4->5, 和 n = 2.
當刪除了倒數(shù)第二個節(jié)點后瑞佩，鏈表變?yōu)?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;
}
}
