leetcode 链表

本次题解包括：

依照leetcode定义自己写的链表创建/打印方法，便于测试
2. Add Two Numbers
19 . Remove Nth Node From End of List
21. Merge Two Sorted Lists
23. Merge k Sorted Lists
24. Swap Nodes in Pairs
25. Reverse Nodes in k-Group
61. Rotate List
86. Partition List
138 . Copy List with Random Pointer
141 . Linked List Cycle
142. Linked List Cycle II
143 . Reorder List
147. Insertion Sort List
148. Sort List
160. Intersection of Two Linked Lists
203 . Remove Linked List Elements
206 . Reverse Linked List
234 . Palindrome Linked List
237 . Delete Node in a Linked List
817. Linked List Components

update:2015-7-14

add a 203 solution code:
- using recursion and reference to delete linklist node which value equals x
- 单项链表递归删除，使用引用

update:2015-06-23

update some codes ,more simple and cool than before.
solve problems 203 and 206

一、链表构建

struct ListNode * createLinklist(int *a, int n)
{
	if (n <= 0) return NULL;
	struct ListNode  *head = (struct ListNode*) malloc(sizeof(struct ListNode)), *p = head, *q;
	head->val = a[0];
	head->next = NULL;
	for (int i = 1; i < n; i++){
		q = (struct ListNode*) malloc(sizeof(struct ListNode));
		q->next = NULL; //怀念c++默认构造函数。。。
		q->val = a[i];
		p->next = q;
		p = q;
	}
	return head;
}

void printLinklist(struct ListNode * head)
{
	for (; head; head = head->next)
		printf("%d  ", head->val);
	puts("");
}

C++

struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};

ListNode * createLinklist(int *a, int n)
{
	if (n <= 0) return NULL;
	ListNode * head = new ListNode(a[0]), *p = head, *q;
	for (int i = 1; i < n; i++){
		q = new ListNode(a[i]);
		p->next = q;
		p = q;
	}
	return head;
}

void printLinklist(ListNode * head)
{
	for (; head; head = head->next)
		printf("%d  ", head->val);
	puts("");
}

Python

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def creatList(vals):
    head=ListNode(-1)
    p=head
    for i in vals:
        q=ListNode(i)
        p.next , p = q, q
    return head.next

def printList(head):
    while head:
        print head.val
        head=head.next

二、题解

2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8

题目地址：leetcode Add Two Numbers

题目大意: 给定两个非空链表，链表已经是逆序，求他们的和。

思路:

利用哨兵节点代码更好写，直接加即可。

C++

class Solution {
public:
	ListNode * addTwoNumbers(ListNode* l1, ListNode* l2) {
		if (!l1) return l2;
		if (!l2) return l1;
		ListNode head(-1), *p = &head, *q = nullptr;
		int carry = 0;
		while (l1 || l2) {
			int t = carry;
			if (l2) {
				t += l2->val;
				l2 = l2->next;
			}
			if (l1) {
				t += l1->val;
				l1 = l1->next;
			}
			q = new ListNode(t < 10 ? t : t - 10);
			carry = t >= 10 ? 1 : 0;
			p->next = q;
			p = q;
		}
		if (carry) {
			q = new ListNode(carry);
			p->next = q;
		}

		p = head.next;
		return p;
	}
};

Java

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(-1), p = head, q;
        int carry = 0;
        while (l1 != null  l2 != null) {
            int t = carry;
            if (l1 != null) {
                t += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                t += l2.val;
                l2 = l2.next;
            }
            q = new ListNode(t >= 10 ? t - 10 : t);
            carry = t >= 10 ? 1 : 0;
            p.next = q;
            p = q;
        }
        if (carry != 0) {
            q = new ListNode(carry);
            p.next = q;
        }
        return head.next;
    }
}

Python

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        head = p = q = ListNode(-1)
        carry = 0
        while l1 or l2:
            t = carry
            if l1:
                t += l1.val
                l1 = l1.next
            if l2:
                t += l2.val
                l2 = l2.next
            q = ListNode(t if t < 10 else t - 10)
            carry = 1 if t >= 10 else 0
            p.next = q
            p = q
        if carry:
            q = ListNode(carry)
            p.next = q
        return head.next

19. leetcode Remove Nth Node From End of List

Given a linked list, remove the _n_th node from the end of list and return its head.

For example,
1
2
3
4
5
Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.
Note: Given n will always be valid. Try to do this in one pass.

题目地址：leetcode Remove Nth Node From End of List

思路：

如果可以求出链表的长度，那么很简单：

class Solution {
public:
	ListNode* removeNthFromEnd(ListNode* head, int n) {
		int len = 0;
		ListNode *p = head , *t;
		while (p) {
			len++; 
			p = p->next;
		}
		int cnt = 0,target = len - n;
		if (!target) {
		    t = head;
		    head = head->next;
		}
		else{
		    p = head;
    		for (int i = 1; i < len - n; i++)
    			p = p->next;
    		t = p->next;
    		p->next = t? t->next:NULL;
		}
		delete t;
		return head;
	}
};

但是如果要求只遍历一次呢，我们就不能求长度了，可以用两个指针，一个指针faster先遍历n个节点，然后在一起遍历到faster->next为空的时候。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *p = head, *q = head;
        for(int i = 0; i < n; ++i)
            q = q->next;
        if(!q){
            q = head;
            head = head->next;
        }
        else{
            while(q->next){
                p = p->next;
                q = q->next;
            }
            q = p->next;
            p->next = q->next;
        }
        delete q;
        return head;
    }
};

Python

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        p = q = head
        for i in range(n):
            q = q.next
        if not q:
            return head.next
        
        while q.next:
            p = p.next
            q = q.next
        p.next = p.next.next
        return head

21. leetcode Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

题目地址：leetcode Merge Two Sorted Lists

题目大意：合并两个已经排好序的链表。

类似归并排序，直接合并即可。

C++:

class Solution {
public:
	ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
		ListNode t(-1), *head = &t;
		ListNode *p = head;
		while (l1 && l2) {
			if (l1->val <= l2->val) {
				p->next = l1;
				l1 = l1->next;
			}
			else {
				p->next = l2;
				l2 = l2->next;
			}
			p = p->next;
		}
		p->next = l1 ? l1 : l2;
		p = head->next;
		return p;
	}
};

Python

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        head = p = ListNode(-1)
        while l1 and l2:
            if l1.val < l2.val:
                p.next = l1
                l1 = l1.next
            else:
                p.next = l2
                l2 = l2.next
            p = p.next
        p.next = l1 if l1 else l2
        return head.next

23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

题目地址：leetcode Merge k Sorted Lists

题目大意：给定k个排好序的链表，合并成一个有序的

思路：

用堆来合并。复杂度O(Nlogk) N为最终合并完的链表的长度。

C++

struct ListNodeCompare{
    bool operator() (ListNode* a, ListNode *b){
        return a->val > b->val;
    }
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, ListNodeCompare> q;
        for(ListNode* head: lists) if(head) q.push(head);
        
        ListNode head(-1), *p = &head;
        while(!q.empty()){
            ListNode* cur = q.top();
            q.pop();
            p->next = cur;
            p = cur;
            if(cur->next){
                q.push(cur->next);
                cur->next = nullptr;
            }
        }
        return head.next;
    }
};

当然也可以新建一个类来做比较

struct MergeNode{
    ListNode *head;
    MergeNode(ListNode *p): head(p){}
    bool operator <(const MergeNode &b) const{
        return head->val > b.head->val;
    }
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode dummy(-1), *p = &dummy;
        priority_queue<MergeNode> q;
        for(ListNode *t: lists) if(t) q.push(MergeNode(t));
        while(!q.empty()){
            MergeNode cur = q.top();
            q.pop();
            p->next = cur.head;
            cur.head = cur.head->next;
            p = p->next;
            p->next = nullptr;
            if(cur.head)
                q.push(cur);
        }
        return dummy.next;
    }
};

Python

class MergeNode(object):
    def __init__(self, head):
        self.head = head
    
    def __lt__(self, other):
        return self.head.val < other.head.val;
        

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        q = []
        for t in lists:
            if t:
                q.append(MergeNode(t))
                
        heapq.heapify(q)
        p = dummy = ListNode(-1)
        while q:
            cur = heapq.heappop(q)
            p.next = cur.head
            cur.head = cur.head.next
            p = p.next
            p.next = None
            if cur.head:
                heapq.heappush(q, cur)
        return dummy.next

24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

For example, Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

题目地址：leetcode Swap Nodes in Pairs

题目大意：交换链表中相邻两个元素

思路：直接交换即可。。。

C++

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode dummy(-1), *p = &dummy;
        p->next = head;
        while(p->next && p->next->next){
            ListNode *a = p->next, *b = a->next;
            p->next = b;
            a->next = b->next;
            b->next = a;
            p = a;
        }
        return dummy.next;
    }
};

Python

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        dummy = p = ListNode(-1)
        p.next = head
        while p.next and p.next.next:
            a, b = p.next, p.next.next
            p.next = b
            a.next = b.next
            b.next = a
            p = a
        return dummy.next

25. Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example, Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

题目地址：leetcode Reverse Nodes in k-Group

题目大意: 给定数字k，要求将这链表分为k组，每组进行逆置

比上面一题难处理一点。

主要是写个逆置的function，每次数到k个数调用。

需要注意的是本题是将链表的块进行调换，而不是交换元素值，需要特别注意调换后和调换前的块的位置关系。

C++

class Solution {
	void reverse(ListNode *head, ListNode *tail) {
		ListNode *tail_next = tail->next, *p = head->next;
		head->next = tail_next;
		while (p != tail_next) {
			ListNode *q = p->next;
			p->next = head;
			head = p;
			p = q;
		}
	}

public:
	ListNode * reverseKGroup(ListNode* head, int k) {
		if (k < 2 || !head) return head;
		ListNode dummy(-1), *p = &dummy;
		p->next = head;

		while (p) {
			ListNode *q = p, *t = p->next;
			for (int i = 0; i < k && q; ++i)
				q = q->next;
			if (!q) break;
			reverse(t, q);
			p->next = q;
			p = t;
		}
		return dummy.next;
	}
};

61. Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

For example: Given 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL.

题目地址：leetcode Rotate List

题目大意: 给定一个链表，和k，要求从结尾开始算起第k个位置旋转到开头

思路：进行两次扫描，第一次扫描算出链表长度并且标记尾部。第二次扫描只需要找到右边算起第 k % len +1的位置即可。

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
	ListNode *rotateRight(ListNode *head, int k) {
		if (!head) return head;
		ListNode *tail, *p = head;
		int len = 0;
		while (p -> next){
			p = p->next;
			len++;
		}
		len++;
		k %= len;
		tail = p;
		p = head;		
		for (int i = 0; i < len - k -1; i++){
			p = p->next;
		}
		tail->next = head;
		head = p->next;
		p->next = NULL;	
		return head;
	}
};

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param head, a ListNode
    # @param k, an integer
    # @return a ListNode
    def rotateRight(self, head, k):
        if not head:
            return head
        p , n = head , 0 
        while p.next:
            p , n = p.next , n + 1  
        n+=1 
        k %= n
        tail , p = p , head
        for i in range(n-k-1):
            p=p.next
        tail.next=head
        head=p.next
        p.next=None
        return head

86. Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example, Given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5.

题目地址：leetcode Partition List

题目大意：给定一个链表和一个数字x，要求对链表元素进行划分。将小于x的元素放在大于等于x元素的左边。

思路：

两个指针一个指向小于的，一个指向大于等于的，然后遍历链表即可。

C++

class Solution {
public:
	ListNode* partition(ListNode* head, int x) {
		ListNode lower(-1), greater(-1);
		ListNode *l = &lower, *g = &greater;
		for (ListNode *p = head; p; p = p->next) {
			if (p->val < x) 
				l = l->next = p;
			else 
				g = g->next = p;
		}
		l->next = greater.next;
		g->next = nullptr; //需要设置为null！，否则g->next可能指向lower的某元素
		return lower.next;
	}
};

Python

class Solution(object):
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        l = left = ListNode(0)
        r = right = ListNode(0)
        while head:
            if head.val < x:
                l.next = head
                l = l.next
            else:
                r.next = head
                r = r.next
            head = head.next
        l.next = right.next
        r.next = None
        return left.next

discuss看到的另一种写法：

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode left(0), right(0);
        ListNode *l = &left, *r = &right;

        while(head){
            ListNode* & ref = head->val < x ? l : r;
            ref->next = head;
            ref = ref->next;
            
            head = head->next;
        }
        l->next = right.next;
        r->next = NULL;
        return left.next;
    }
};

138 . Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

题目地址：leetcode Copy List with Random Pointer

题目大意：给定一个链表，链表中有个指针random，它随机指向该链表中的任何结点，现在请你复制这个链表（深度复制）

思路：需要深度复制的话，难点在于如何更改random指针，而不是照搬。（照搬的话原链表要是修改那么你random输出的也会被改）我直接用字典(dict c++也叫map)了。

/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
    unordered_map<RandomListNode *, RandomListNode *> vis;
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        if(!head) return head;
        if(vis.find(head) != vis.end()) return vis[head];
        RandomListNode *new_head =  new RandomListNode(head->label);
        vis[head] = new_head;
        new_head ->next = copyRandomList(head->next);
        new_head ->random = copyRandomList(head->random);
        return new_head;
    }
};

Python

# Definition for singly-linked list with a random pointer.
# class RandomListNode(object):
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None

class Solution(object):
    def __init__(self):
        self.dic = {}
        
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        if not head: return head
        if head in self.dic:
            return self.dic[head]
        self.dic[head] = RandomListNode(head.label)
        self.dic[head].next = self.copyRandomList(head.next)  
        self.dic[head].random = self.copyRandomList(head.random)  
        return self.dic[head]

141. Linked List Cycle

Given a linked list, determine if it has a cycle in it.

Follow up: Can you solve it without using extra space?

题目地址：leetcode Linked List Cycle

题意：给一个链表，判断其是否有环。

思路：假设两个小孩一直在绕操场跑，其中小孩A速度是小孩B的两倍，那么A一定会一次次的“追上”小孩B。所以两个指针，一个每次前进一步，一个两步，直到为空（无环）或者相等为止（有环）

bool hasCycle(struct ListNode *head) {
	struct ListNode *p = head, *q = head;
	while (q && q->next) {
		p = p->next;
		q = q->next->next;
		if (p == q) return true;
	}
	return false;
}

C++

class Solution {
public:
	bool hasCycle(ListNode *head) {
		ListNode *p = head, *q = head;
		while (q && q->next) {
			p = p->next;
			q = q->next->next;
			if (p == q) return true;
		}
		return false;
	}
};

Java

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode p = head, q = head;
        while (q != null && q.next != null) {
            p = p.next;
            q = q.next.next;
            if(p == q) return true;
        }
        return false;
    }
}

Python

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        p = q = head
        while q and q.next:
            p = p.next
            q = q.next.next
            if p == q: return True
        return False

142. Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up: Can you solve it without using extra space?

题目地址：leetcode Linked List Cycle II

题意：给一个链表，返回其开始环的地方，如果没有，返回NULL

思路：

同样的判圈法（见下面详细说明）
hash表：遍历的同时存进hash表，若遇到重复的返回即可。

方法一：

上面的判断有圈子的方法我们在回顾一下：

fast指针的速度为慢指针slow的两倍，如果有环，那么fast指针一定会追上慢指针slow！

如上图所示：假设非环的部分长为a，第一次相遇点z离环的起点的y距离为b，slow指针在环上移动的距离不会超过一圈，为什么？考虑极端的情况，就是没有上图a那一段，那么快慢指针同时从y点出发，第一次相遇则恰好在y点处。而如果有a那一段的话，就不会走到y点了。

那么有：

slow 指针距离= a + b
fast指针距离 = a + b + c + b

由于fast是slow的两倍，因此有

2(a + b) = (a + b + c + b)
化简得 a = c

因此，当有环的时候，fast和slow相遇为z那么将fast或者slow重新指向开头head，然后各走a步，就会相遇于点y

换句话说：在z处走c也会回到y，从head走c也到达y。

C++

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
		ListNode *p = head, *q = head;
		while (q && q->next) {
			p = p->next;
			q = q->next->next;
			if (p == q) break;
		}
		if (!q || !q->next) return NULL;
		q = head;
		while (p != q) {
			p = p->next;
			q = q->next;
		}
		return p;
    }
};

Java

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode p = head, q = head;
        while (q != null && q.next != null) {
            p = p.next;
            q = q.next.next;
            if (p == q) break;
        }
        if (q == null  q.next == null) return null;
        q = head;
        while (p != q) {
            p = p.next;
            q = q.next;
        }
        return p;
    }
}

Python

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        fast = slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                break
        if not fast or not fast.next: return None
        fast = head
        while fast != slow:
            fast = fast.next
            slow = slow.next
        return fast

方法二hash：（C的话得手写hash=v=懒）

C++

class Solution {
public:
	ListNode *detectCycle(ListNode *head) {
		if (head == NULL) return NULL;
		unordered_set<ListNode *> dic;
		dic.insert(head);
		while (head){
			head = head->next;
			if (dic.find(head) != dic.end())return head;
			dic.insert(head);
		}
		return NULL;
	}
};

Python

class Solution:
    # @param head, a ListNode
    # @return a list node
    def detectCycle(self, head):
        if not head : return None
        dic = set([head])
        while head:
            head=head.next
            if head in dic:
                return head
            dic.add(head)
        return None

143. Reorder List

Given a singly linked list L: _L_0→_L_1→…→_L__n_-1→_L_n, reorder it to: _L_0→_L__n_→_L_1→_L__n_-1→_L_2→_L__n_-2→…

You must do this in-place without altering the nodes' values.

For example, Given {1,2,3,4}, reorder it to {1,4,2,3}.

题目地址：leetcode Reorder List

题目大意：给定一个链表 L0→L1→…→Ln-1→Ln,，返回L0→Ln→L1→Ln-1→L2→Ln-2的顺序

思路：分为3步：

求中点（可以先遍历找到中点，但更好的是快慢指针）
翻转后面的链表
两个链表合并

C++

class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head) return;
        ListNode *p = head, *q = head;
        while(q->next && q->next->next){
            p = p->next;
            q = q->next->next;
        }
        q = p->next;
        p->next = nullptr;
        
        ListNode *head2 = reverse(q);
        q = head2;
        
        while(head && head2){
            p = head->next;
            head->next = head2;
            q = head2->next;
            head2->next = p;
            head = p;
            head2 = q;
        }
    }
    
    ListNode *reverse(ListNode *head){
        if(!head) return head;
        ListNode *p = head->next;
        ListNode *new_head = head;
        while(p){
            head->next = p->next;
            p->next = new_head;
            new_head = p;
            p = head->next;
        }
        return new_head;
    }
};

Python

class Solution:
    # @param head, a ListNode
    # @return nothing
    def reorderList(self, head):
        if not head or not head.next:return
        p ,n = head , 0
        while p:     p , n= p.next,n+1 #get length
        mid ,p= n>>1,head
        for i in xrange(mid):
            p=p.next
        rhead= self.reverseList(p)

        while rhead.next:
            t , p= head.next,rhead.next
            head.next=rhead
            rhead.next =head= t         
            rhead=p
            
    def reverseList(self,head):
        cur ,pre=head.next,head
        while cur:
            next = cur.next
            cur.next ,pre.next = head,next
            head,cur=cur,next
        return head

class Solution(object):
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: void Do not return anything, modify head in-place instead.
        """
        if not head or not head.next: return
        p, q = head, head.next
        while q and q.next:
            p, q = p.next, q.next.next

        pre = rhead = p.next
        cur = rhead.next
        p.next = None
        while cur:  # reverse a list
            next = cur.next
            cur.next, pre.next = rhead, next
            rhead, cur = cur, next

        p, q = head, rhead
        while q:
            t = q.next
            q.next, p.next = p.next, q
            p, q = p.next.next, t

147. leetcode Insertion Sort List

Sort a linked list using insertion sort.

题目地址：leetcode Insertion Sort List

题意：对一个链表进行插入排序

思路：用tail标记包括tail之前已排好序的链表。对于cur=tail.next，先和tail比较，若大于等于，则不用排序，否则从头开始查找插入位置。

还有就是我用了哨兵结点，便于插入。

C/C++

struct ListNode* insertionSortList(struct ListNode* head) {
	if (!head) return head;
	struct ListNode *newHead = (struct ListNode*)malloc(sizeof(struct ListNode));
	newHead->next = head;
	struct ListNode *pre_p = head, *p = pre_p->next;
	while (p){
		struct ListNode *pre_q = newHead, *q = pre_q->next;
		while (q->val <= p->val && p != q){//有序
			pre_q = q;
			q = q->next;
		}
		if (p != q) {
			pre_p->next = p->next;
			pre_q->next = p;
			p->next = q;
		}
		else
			pre_p = pre_p->next;
		p = pre_p->next;
	}
	head = newHead->next;
	free(newHead);
	return head;
}

Python

class Solution:
    # @param head, a ListNode
    # @return a ListNode
    def insertionSortList(self, head):
        if not head or not head.next:return head
        p = ListNode(-1)
        p.next, head=head,p
        tail =  head.next
        while tail.next:
            cur =tail.next
            if tail.val <= cur.val :
                tail = tail.next
            else:
                p ,prep= head.next,head
                while p.val < cur.val:
                    prep,p=prep.next,p.next
                self.delNode(tail,cur)
                self.insertNode(prep,cur)
        return head.next

    #del p from list, pre is previous node
    def delNode(self,pre,p):
        pre.next=p.next

    #insert p from list, pre is previous node
    def insertNode(self,pre,p):
        p.next , pre.next = pre.next , p

148. leetcode Sort List

Sort a linked list in O(n log n) time using constant space complexity.

题目地址：leetcode Sort List

题意：给定一个链表，要求用O(n log n) 的复杂度进行排序。

思路：合并排序或者快排都行

class Solution:
    # @param head, a ListNode
    # @return a ListNode
    def sortList(self, head):
        if  not head or not head.next :return head
        p , one,two=ListNode(0),head,head
        p.next=head
        while two and two.next:
            p = one
            one , two = one.next,two.next.next
        p.next=None       
        lhead=self.sortList(head)
        rhead=self.sortList(one)
        return self.merge(lhead,rhead)

    def merge(self,lhead,rhead):       
        head = ListNode(-1)
        p,prep=None,head
        while lhead and rhead:
            if lhead.val < rhead.val:
                p ,lhead= lhead,lhead.next
            else:
                p,rhead=rhead,rhead.next
            prep.next=p
            prep=prep.next
        
        while lhead:
            p , lhead= lhead,lhead.next
            prep.next=p
            prep=prep.next
        while rhead:
            p,rhead=rhead,rhead.next
            prep.next=p
            prep=prep.next

        return head.next

160. leetcode Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:
1
2
3
4
5
A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3
begin to intersect at node c1.

Notes:

If the two linked lists have no intersection at all, return null.

The linked lists must retain their original structure after the function returns.

You may assume there are no cycles anywhere in the entire linked structure.

Your code should preferably run in O(n) time and use only O(1) memory.

题目地址：leetcode Intersection of Two Linked Lists

题意：给定两个链表，返回其重复的第一个位置。

思路：

用哈希表O(n+m) 空间为O(m)或者O(n)
由于两个链表可能一长一短，故对其同时进行遍历时一定有一个先到达结尾。如果链表A先到结尾，则指向B的开头，如果B先到达结尾，则指向A的开头。然后继续进行遍历，这样两个链表一定同时到达结尾。当到达结尾时，如果之前最早出现过两个指针指向地址相同的，那么就是所求解。这样正确的原因在于，如果两个链表尾部有重复的，那么两个链表链接起来不管是a+b还是b+a尾部也一定是一样的。- - 然后长度还一样，没啥好说的了。

方法一(hash)

c 的hash表(介绍详见leetcode哈希表)

Python

class Solution:
    # @param two ListNodes
    # @return the intersected ListNode
    def getIntersectionNode(self, headA, headB):
        dic=set()
        while headA:
            dic.add(headA)
            headA=headA.next
        while headB:
            if headB in dic:
                return headB
            headB=headB.next
        return None

方法二

C++

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* p = headA;
        ListNode* q = headB;
        while (p != q) {
            p = p ? p->next : headB;
            q = q ? q->next : headA;
        }
        return p;
    }
};

Java

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null  headB == null) return null;
        ListNode p = headA, q = headB;
        while (p != null  q != null) {
            if (p == null) p = headB;
            if (q == null) q = headA;
            if(p == q) return p;
            p = p.next;
            q = q.next;
        }
        return null;
    }
}

Python

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        p, q = headA, headB
        while p != q:
            p = p.next if p else headB
            q = q.next if q else headA
        return p

203. leetcode Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.

Example Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6 Return: 1 --> 2 --> 3 --> 4 --> 5

题目地址：leetcode Remove Linked List Elements

题意：给定一个链表，删除值为val的全部元素

思路：

建一个哨兵节点统一删除操作，这个没啥好说的，代码在比较下面
使用C++引用+递归

C++ 引用+递归

单向链表使用引用的递归删除。

当L->val == x时候，当前的结点为待删除的结点，故用指针指向当前结点（p = L)，并且让当前结点指向下一个结点(L=L->next)，之后我们删除该结点(delete p)，并且调用del_x(L,x); （毕竟现在的L可能也等于x）
当L->val != x时候，当前结点并不是要删除的结点，调用del_x(L->next,x);

我们知道，在非递归版本中，我们每次记录前项，然后删除的时候将该结点的前结点指向该结点的下一个结点。

使用引用的话，可以不用记录前项，而且不会产生断链。

为什么？以1，2，3 删除数为2 为例子。（下面把1 ， 2， 3 内存地址称为A,B,C，方便说明）

初始L指向A，非待删除结点，执行 del_x(L->next,x); 此时L->next 指向了B
L指向B，需要删除， L = L->next 的时候，因为此时的L使用引用，其值为A->next，效果等同于A->next = B ->next 就是说A->next指向了C，删除B后，执行del_x(L,x);
L指向C，非待删除，调用del_x(L->next,x);
L为NULL，return

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
	void del_x(ListNode* &L,int x){
		if(L == NULL) return;
		if(L->val == x){
			ListNode *p = L;
			L = L->next;
			delete p;
			del_x(L,x);	
		}
		else
			del_x(L->next,x);	
	}
    ListNode* removeElements(ListNode* head, int val) {
        del_x(head,val);
        return head;  
    }
};

struct ListNode* removeElements(struct ListNode* head, int val) {
	struct ListNode* newHead = (struct ListNode*) malloc(sizeof(struct ListNode));
	newHead->next = head;					//新建个头结点（哨兵节点）统一操作
	struct ListNode *p = newHead, *q = head; //q为p后一个元素
	while (q)
	{
		if (q->val == val){
			p->next = q->next;
			free(q);
		}
		else
			p = p->next;
		q = p->next;
	}
	struct ListNode* res = newHead->next;
	free(newHead);
	return res;
}

C++

class Solution {
public:
	ListNode* removeElements(ListNode* head, int val) {
		ListNode* newHead = new ListNode(-1);
		newHead->next = head;					//新建个头结点（哨兵节点）统一操作
		ListNode *p = newHead, *q = head; //q为p后一个元素
		while (q)
		{
			if (q->val == val){
				p->next = q->next;
				delete q;
			}
			else p = p->next;
			q = p->next;
		}
		ListNode* res = newHead->next;
		delete newHead;
		return res;
	}
};

Python

class Solution:
    # @param {ListNode} head
    # @param {integer} val
    # @return {ListNode}
    def removeElements(self, head, val):
        if not head: return head
        p = newHead = ListNode(-1)
        newHead.next = q =head
        while q:
            if q.val == val: p.next=q.next 
            else:   p = p.next
            q = q.next
        return newHead.next

206. leetcode Reverse Linked List

Reverse a singly linked list.

题目地址：leetcode Reverse Linked List

题意：链表逆序

思路：每次遍历到某个元素把它变为“头”即可

struct ListNode* reverseList(struct ListNode* head) {
	if (!head) return head; //head 为NULL
	struct ListNode *p = head, *q = head->next;
	while (q){
		p->next = q->next;
		q->next = head;
		head = q;
		q = p->next;
	}
	return head;
}

C++(和C差不多，不必看)

class Solution {
public:
	ListNode* reverseList(ListNode* head) {
		if (!head) return head; //head 为NULL
		ListNode *p = head, *q = head->next;
		while (q){
			p->next = q->next;
			q->next = head;
			head = q;
			q = p->next;
		}
		return head;
	}
};

python (其实都差不多好不好 (╯‵□′)╯︵┻━┻)

class Solution:
    # @param {ListNode} head
    # @return {ListNode}
    def reverseList(self, head):
        if not head:return head
        p ,q =head, head.next
        while q:
            p.next = q.next
            q.next = head
            head = q
            q = p.next
        return head

另外一种方法

方法2:

cur和pre双指针，每次pre为cur后面一个元素，遍历的时候将pre->next指向cur即可

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head:
            return head
        cur = None
        pre = head
        while pre:
            temp = pre.next
            pre.next = cur
            cur = pre
            pre = temp
        return cur

C++

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr) {
            return head;
        }
        ListNode* p = nullptr;
        ListNode* q = head;
        while (q != nullptr) {
            ListNode* temp = q->next;
            q->next = p;
            p = q;
            q = temp;
        }
        return p;
    }
};

234. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Follow up: Could you do it in O(n) time and O(1) space?

题目地址：leetcode Palindrome Linked List

题意：给定一个链表，判断它是否为回文串

思路：最简单的方法是直接保存下来对比一下时间空间复杂度均为O(n)

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        t = []
        while head:
            t.append(head.val)
            head = head.next
        return t == t[::-1]

第二种方法是将链表分为两半，前一半或者后一半逆序然后比较。

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head or not head.next: return True
        slow = fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        right = self.reverse_list(slow.next)
        left = head

        while right:
            if left.val != right.val: return False
            left, right = left.next, right.next
        return True

    def reverse_list(self, head):
        p, head.next = head.next, None
        while p:
            next, p.next = p.next, head
            head, p = p, next
        return head

237 Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

题目地址：leetcode Delete Node in a Linked List

题意：给定指向要删除的节点的指针，删除这个节点。

思路：把这个指针内容复制为下一个，然后删除下一个即可。

C++

class Solution {
public:
    void deleteNode(ListNode* node) {
        ListNode * next = node->next;
        *node = *next;
        delete next;
    }
};

Python

class Solution(object):
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        node.val = node.next.val
        node.next = node.next.next

817. Linked List Components

We are given head, the head node of a linked list containing unique integer values.

We are also given the list G, a subset of the values in the linked list.

Return the number of connected components in G, where two values are connected if they appear consecutively in the linked list.

Example 1:

Input: head: 0->1->2->3 G = [0, 1, 3] Output: 2 Explanation: 0 and 1 are connected, so [0, 1] and [3] are the two connected components.

Example 2:

Input: head: 0->1->2->3->4 G = [0, 3, 1, 4] Output: 2 Explanation: 0 and 1 are connected, 3 and 4 are connected, so [0, 1] and [3, 4] are the two connected components.

Note:

If N is the length of the linked list given by head, 1 <= N <= 10000. The value of each node in the linked list will be in the range [0, N - 1]. 1 <= G.length <= 10000. G is a subset of all values in the linked list.

题目地址：leetcode Linked List Components

题目大意：给定一个链表和一个数组G，让你判断G中包含链表中几个“连接的部分”。连接的部分定义为：两个值连续出现即为一个连接部分。

思路：把G变为set，遍历数组，记录前一个是否为连接的从而进行分组。

C++

class Solution {
public:
    int numComponents(ListNode* head, vector<int>& G) {
        if(!head) return 0;
        int cnt = 0;
        bool pre_in = false;
        unordered_set<int> g(G.begin(), G.end());
        for(; head; head = head->next){
            if(g.find(head->val) != g.end()){
                if(!pre_in){
                    pre_in = true;
                    ++cnt;
                }
            }
            else
                pre_in = false;
        }
        return cnt;
    }
};

Python

class Solution(object):
    def numComponents(self, head, G):
        """
        :type head: ListNode
        :type G: List[int]
        :rtype: int
        """
        if not head: return 0
        pre_in = False
        G = set(G)
        cnt = 0
        while head:
            if head.val in G:
                if not pre_in:
                    pre_in = True
                    cnt += 1
            else:
                pre_in = False
            head = head.next
        return cnt

更多题解可以查看： https://www.hrwhisper.me/leetcode-algorithm-solution/