( 1 ) 题目描述:
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交点，返回 null 。
( 2 ) 输入输出描述：
输入：intersectVal = 8 , listA = [ 4,1 ,8,4,5] , listB = [ 5,6 ,1,8,4,5] , skipA = 2 , skipB = 3
输出：Intersected at '8' 关键思路：
定义两个节点同时从两个链表遍历，遍历到头后，从另一个链表开始遍历，到相遇处就是交点
class Solution {
public : ListNode * getIntersectionNode ( ListNode * headA, ListNode * headB) { ListNode * A = headA; ListNode * B = headB; while ( A != B) { A = ( A == NULL ) ? headB: A-> next; B = ( B == NULL ) ? headA: B-> next; } return A; }
} ;
( 1 ) 题目描述:
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
( 2 ) 输入输出描述：
输入：head = [ 1,2 ,3,4,5]
输出：[ 5,4 ,3,2,1] 关键思路：
从链表头开始遍历，cur保留当前节点，每次遍历更新pre cur_next位置
class Solution {
public : ListNode* reverseList ( ListNode* head) { ListNode* cur = head; ListNode* pre = nullptr ; ListNode* cur_next = nullptr ; while ( cur != nullptr ) { cur_next = cur-> next; cur-> next = pre; pre = cur; cur = cur_next; } return pre; }
} ;
( 1 ) 题目描述:
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
( 2 ) 输入输出描述：
输入：head = [ 1,2 ,2,1]
输出：true关键思路：
先遍历链表，用数组承接链表元素，接着使用双指针判断数组首尾元素是否一直相等。
class Solution {
public : bool isPalindrome ( ListNode* head) { vector< int > record; ListNode* phead = head; int left, right; if ( head == nullptr ) return false ; while ( phead) { record. push_back ( phead-> val) ; phead = phead-> next; } left = 0 ; right = record. size ( ) - 1 ; while ( left<= right) { if ( record[ left] != record[ right] ) return false ; left++ ; right-- ; } return true ; }
} ;
( 1 ) 题目描述:
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。( 2 ) 输入输出描述：
输入：head = [ 3,2 ,0,-4] , pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。关键思路：
使用快慢双指针遍历链表，快指针每次走两步，慢指针走1步。
若存在环，总会相遇。
class Solution {
public : bool hasCycle ( ListNode * head) { ListNode* fast = head; ListNode* slow = head; while ( fast && fast-> next) { slow = slow-> next; fast = fast-> next-> next; if ( slow == fast) return true ; } return false ; }
} ;
( 1 ) 题目描述:
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。( 2 ) 输入输出描述：
输入：head = [ 3,2 ,0,-4] , pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。关键思路：
使用快慢双指针遍历链表，快指针每次走两步，慢指针走1步。若存在环，总会相遇。
相遇后要找到环的入口节点。x+n*( y+z) = 2 *( x+y) ,假如在y点相遇。相遇后快指针移到开头，快慢指针同时向后遍历，相遇处即交点。
class Solution {
public : ListNode * detectCycle ( ListNode * head) { ListNode* fast = head; ListNode* slow = head; while ( 1 ) { if ( fast && fast-> next) { fast = fast-> next-> next; slow = slow-> next; if ( fast == slow) break ; } else return NULL ; } fast = head; while ( fast != slow) { fast = fast-> next; slow = slow-> next; } return fast; }
} ;
( 1 ) 题目描述:
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 ( 2 ) 输入输出描述：
输入：l1 = [ 1,2 ,4] , l2 = [ 1,3 ,4]
输出：[ 1,1 ,2,3,4,4] 关键思路：
定义数组保存两个链表中各项的值，对于每个值开辟节点保存到链表中
class Solution {
public : ListNode* mergeTwoLists ( ListNode* list1, ListNode* list2) { ListNode* p = list1; if ( list1 == NULL && list2 == NULL ) return NULL ; vector< int > record; while ( p) { record. push_back ( p-> val) ; p = p-> next; } p = list2; while ( p) { record. push_back ( p-> val) ; p = p-> next; } sort ( record. begin ( ) , record. end ( ) ) ; ListNode* head = new ListNode ( record[ 0 ] ) ; p = head; for ( int i = 1 ; i< record. size ( ) ; i++ ) { ListNode* tmp = new ListNode ( record[ i] ) ; p-> next = tmp; p = p-> next; } return head; }
} ;
( 1 ) 题目描述:
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。( 2 ) 输入输出描述：
输入：l1 = [ 2,4 ,3] , l2 = [ 5,6 ,4]
输出：[ 7,0 ,8]
解释：342 + 465 = 807 .关键思路：
遍历两个链表，将其值相加得到record，创建新节点保存各项值的个位，然后record保存值的十位，然后平移cur节点，进入下一轮循环。
class Solution {
public : ListNode* addTwoNumbers ( ListNode* l1, ListNode* l2) { ListNode* dummy = new ListNode ( 0 ) ; ListNode* cur = dummy; int record = 0 ; while ( l1|| l2|| record) { if ( l1) { record += l1-> val; l1 = l1-> next; } if ( l2) { record += l2-> val; l2 = l2-> next; } cur-> next = new ListNode ( record% 10 ) ; cur = cur-> next; record /= 10 ; } return dummy-> next; }
} ;
( 1 ) 题目描述:
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。( 2 ) 输入输出描述：
输入：head = [ 1,2 ,3,4,5] , n = 2
输出：[ 1,2 ,3,5] 关键思路：
定义快慢指针，快指针先走N步，接着快慢指针同时向后遍历，快指针遍历到末尾时，慢指针指向的是待删除元素的前一节点。跳过节点即可，
class Solution {
public : ListNode* removeNthFromEnd ( ListNode* head, int n) { ListNode* dummyhead = new ListNode ( ) ; dummyhead-> next = head; ListNode* fast = dummyhead; ListNode* slow = dummyhead; while ( n-- ) { fast = fast-> next; } while ( fast-> next != nullptr ) { fast = fast-> next; slow = slow-> next; } slow-> next = slow-> next-> next; return dummyhead-> next; }
} ;
( 1 ) 题目描述:
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。( 2 ) 输入输出描述：
输入：head = [ 1,2 ,3,4]
输出：[ 2,1 ,4,3] 关键思路：
交换两个节点要保留四个节点，chang1、change2、pre、nect_change；做完赋值后，开始构建链表。
class Solution {
public : ListNode* swapPairs ( ListNode* head) { ListNode* pre = new ListNode ( ) ; pre-> next = head; ListNode* dummyhead = pre; ListNode* next_change1 = nullptr ; ListNode* change1 = nullptr ; ListNode* change2 = nullptr ; while ( ( pre-> next != nullptr ) && ( pre-> next-> next != nullptr ) ) { change1 = pre-> next; change2 = pre-> next-> next; next_change1 = pre-> next-> next-> next; pre-> next = change2; change2-> next = change1; change1-> next = next_change1; pre = change1; } return dummyhead-> next; }
} ;
( 1 ) 题目描述:
深拷贝随机链表关键思路：
使用map< Node*,Node*> 进行链表拷贝，先遍历链表，一个cur对应一个拷贝出来的新节点。此时只是在哈希表中保存了所有节点。
接着再次遍历链表，进行哈希表节点的链接。
class Solution {
public : Node* copyRandomList ( Node* head) { unordered_map< Node* , Node* > record; Node* cur = head; for ( cur = head; cur; cur = cur-> next) { record[ cur] = new Node ( cur-> val) ; } for ( cur = head; cur; cur = cur-> next) { if ( cur-> next) record[ cur] -> next = record[ cur-> next] ; if ( cur-> random) record[ cur] -> random = record[ cur-> random] ; } return record[ head] ; }
} ;
( 1 ) 题目描述:
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 ( 2 ) 输入输出描述
输入：head = [ 4,2 ,1,3]
输出：[ 1,2 ,3,4] 关键思路：
遍历链表，将链表各节点值保存至数组中，对数组排序，接着再遍历链表，修改链表中各节点值
class Solution {
public : ListNode* sortList ( ListNode* head) { vector< int > record; ListNode * phead = head; while ( phead) { record. push_back ( phead-> val) ; phead = phead-> next; } sort ( record. begin ( ) , record. end ( ) ) ; phead = head; int k = 0 ; while ( phead) { phead-> val = record[ k++ ] ; phead = phead-> next; } return head; }
} ;
