算法与数据结构-链表
2018-01-05 本文已影响24人
sylvainwang
按Tags的顺序来了：
- Remove Nth Node From End of List
移除链表倒数第N个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.
快慢指针的方法，快指针先往前走，可以自己画个图理解，因为要去掉倒数第N个节点，因此慢指针要停在倒数第N+1处，因此快指针先往前走N+1步。
特别注意：如果快指针先走的时候就碰到了指针元素为NULL的情况，说明要去除的节点是第一个节点，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两个排好序的链表，这种问题和归并排序差不多，代码结构一样
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
反转单链表
添加一个tail节点，初始为None，new为head的下一个，指针变化 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的交点，A,B相交之后后面的所有元素都相同。
链表交点.png
先判断两个列表的长短，付给长短两个变量，长链表先走diff步，然后两个一起往后走，直到一样。
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
只保留出现一次的元素
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
