按Tags的順序來(lái)了：
- Remove Nth Node From End of List
移除鏈表倒數(shù)第N個(gè)node
Given a linked list, remove the nth node from the end of list and return its head.
For example,
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.
快慢指針的方法，快指針先往前走沥匈，可以自己畫(huà)個(gè)圖理解神帅，因?yàn)橐サ舻箶?shù)第N個(gè)節(jié)點(diǎn)，因此慢指針要停在倒數(shù)第N+1處胳岂，因此快指針先往前走N+1步编整。
特別注意：如果快指針先走的時(shí)候就碰到了指針元素為NULL的情況，說(shuō)明要去除的節(jié)點(diǎn)是第一個(gè)節(jié)點(diǎn)乳丰，return head.next
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
fast = head
slow = head
for i in range(n+1):
if fast is not None:
fast = fast.next
else:
return head.next
while fast is not None:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return head
- 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.
Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
Merge兩個(gè)排好序的鏈表掌测，這種問(wèn)題和歸并排序差不多，代碼結(jié)構(gòu)一樣
class Solution(object):
def mergeTwoLists(self, l1, l2):
dummy = ListNode(0)
a = dummy
while l1 and l2:
if l1.val <= l2.val:
a.next = l1
a = a.next
l1 = l1.next
else:
a.next = l2
a = a.next
l2 = l2.next
if l1:
a.next = l1
if l2:
a.next = l2
return dummy.next
- Reverse Linked List
反轉(zhuǎn)單鏈表
添加一個(gè)tail節(jié)點(diǎn)产园，初始為None汞斧，new為head的下一個(gè)，指針變化 head指向tail, tail和head再分別往前走一步
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return None
tail = None
while head:
new = head.next
head.next = tail
tail = head
head = new
return tail
-
Intersection of Two Linked Lists
返回鏈表A,B的交點(diǎn)什燕，A,B相交之后后面的所有元素都相同粘勒。
鏈表交點(diǎn).png
先判斷兩個(gè)列表的長(zhǎng)短，付給長(zhǎng)短兩個(gè)變量屎即，長(zhǎng)鏈表先走diff步庙睡，然后兩個(gè)一起往后走，直到一樣技俐。
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
l1 = self.length(headA)
l2 = self.length(headB)
diff = abs(l1 - l2)
if l1 >= l2:
longlist = headA
shortlist = headB
else:
longlist = headB
shortlist = headA
for i in range(diff):
longlist = longlist.next
while longlist and shortlist and longlist != shortlist:
longlist = longlist.next
shortlist = shortlist.next
return shortlist
def length(self,head):
if not head:
return 0
length = 0
while head:
length += 1
head = head.next
return length
- Remove Duplicates from Sorted List
Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
cur = head
while cur:
if cur.next is not None and cur.next.val == cur.val:
cur.next = cur.next.next
else:
cur = cur.next
return head
- Remove Duplicates from Sorted List II
只保留出現(xiàn)一次的元素
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
dummy = ListNode(0)
pre = dummy
dummy.next = head
while head and head.next:
if head.val == head.next.val:
while head and head.next and head.val == head.next.val:
head = head.next
head = head.next # one more step
pre.next = head
else:
pre = pre.next
head = head.next
return dummy.next
