一、链表的反转

示例：

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

分析：刚开始的时候很自然的想到，创建一个列表，然后遍历链表，将每个节点保存在列表中，然后根据列表，反向构造一个新的链表。但是这个很明显很low，一方面是空间复杂度为O(n)，一方面是要遍历两遍。后来想都到了另外一种方法，只需要遍历一遍，然后所需的额外空间也非常少。
核心思想就是：遍历链表，创建一个新节点，保存当前节点的值。一个节点指向None，将第二个元素指向第一个节点，第三个指向第二个，以此类推。
代码查考如下：

def reverseList( head):
        q = head
        f = None
        while q:
            new = ListNode(q.val)
            new.next = f
            f = new
            q = q.next
        return f

二、删除链表的倒数第N个节点

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

分析：
最容易想到的思路大致如下：先遍历一遍链表，求链表的长度，然后再次遍历，删除倒数的第N个节点。这种思路比较简单，自然效率也比较低。这种思路的具体代码就不加上了。
下面来看一种更为精妙的解法：设置两个指针，一个指针先走N步，然后两个指针一起走，当前面的指针走到链表尾部时，后面的指针下个元素就是要删除的元素。

def removeNthFromEnd(head, n):
        p1, p2 = head, head
        while n:
            p2 = p2.next
            n -= 1
        if p2 is None:
            return head.next
        while 1:
            if p2.next is None:
                p1.next = p1.next.next
                return head
            p1, p2 = p1.next, p2.next

三、求链表的中间节点

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

分析：跟上面的那个题目类似，设置两个指针，一个走一步，一个走两步，当这快指针走到None时，返回慢指针即可

def middleNode(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        p1 = head 
        p2 = head
        while p2 and p2.next:
            p1 = p1.next
            p2 = p2.next.next
        return p1

四、判断链表中是否有环

分析：
同样通过两个指针，一个每次移动一步，一个每次移动两步，如果存在环，那么这两个指针一定会相遇。

代码如下：

def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        p,q = head,head
        while 1:
            if q is None or q.next is None :return False
            p = p.next
            q = q.next.next
            if p is q: 
                return True

五、找到环的入口

题目描述：
给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
分析：
这题解法非常精妙，先按照上题思路，设置两个指针判断链表是否存在环，如果存在，让快指针回到链表开头，然后速度和慢指针一样设置为1，当再次相遇时，就是环的入口。
设起点到环入口距离为a,环入口到相遇点距离为b,相遇时慢指针走了n步。然后从相遇的点开始，快指针回到链表表头，然后速度也变为。

六判断两个链表是否相交

分析：常见的解法有如下几种
*直接循环一个链表，看看这个链表每个元素是否在另外一个链表中。显然这个方法非常低效，时间复杂度为。O(n^2)
*针对第一个链表做一个哈希表，python中可以利用字典，然后再去遍历第二个链表，这种方法时间复杂度为O(n)，但是空间复杂度也上升到O(n)
*将一个链表接到另外一个链表之后，如果是相交这那么新链表一定会形成一个环，然后利用上面的方法进行判读即可。这里还有更简单的方法，就是如果成环，那么第二个链表的表头一定在环上，这时候只要直接遍历第二个链表，看看会不会回到表头即可。
*最后这种是最简单的。如果两个链表相交，那么他们的最后一个为节点一定是相同的，所以只要判断最后一个节点是否相同即可，时间复杂度O(n)空间O(1)

def fun(head1,head2):
    while head1.next:
        head1 = head1.next
    while head2.next:
        head2 = head2.next
    if head1 == head2:return True
    else:return  False

七、找到相交链表的起始节点

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

返回c1，如果不相交返回None
分析：先用上面的方法判断时候相关，同时记录链表长度，若相关求出长度差n，然后利用两个指针，长的链表先走n步，然后同时开始遍历，第一个相同的节点就是相交节点。

def getIntersectionNode(headA, headB):
        if headA is None or headB is None:return None
        l1 ,l2 = 0,0
        p1,p2 = headA,headB
        tail_1,tail_2 = None,None
        while 1:
            l1+=1
            if p1.next is None:
                tail_1 = p1
                break;
            p1 = p1.next
        while p2:
            l2 += 1
            if p2.next is None:
                tail_2 = p2
                break;
            p2 = p2.next
        if tail_1 != tail_2:return None
        else:
            n = abs(l1 -l2)
            if l1 >= l2:
                while n:
                    headA = headA.next
                    n-=1
            else:
                while n:
                    headB = headB.next
                    n-=1
            while 1:
                if headA == headB:return headB
                else:
                    headA,headB = headA.next,headB.next

链表常见题目--附具体分析和代码