go语言快速刷《程序员面试金典》（3）
编写程序以 x 为基准分割链表，使得所有小于 x 的节点排在大于或等于 x 的节点之前。如果链表中包含 x，x 只需出现在小于 x 的元素之后(如下所示)。分割元素 x 只需处于“右半部分”即可，其不需要被置于左右两部分之间。
示例:
输入: head = 3->5->8->5->10->2->1, x = 5
输出: 3->1->2->10->5->5->8
一趟分离，然后连起来即可。
-
/**
-
* Definition for singly-linked list.
-
* type ListNode struct {
-
* Val int
-
* Next *ListNode
-
* }
-
*/
-
func partition(head *ListNode, x int) *ListNode {
-
if head == nil{
-
return nil
-
}
-
dummnyhead1,dummnyhead2 := &ListNode{-1,nil},&ListNode{-1,nil}
-
cur1,cur2 := dummnyhead1,dummnyhead2
-
cur := head
-
for cur != nil{
-
if cur.Val <x{
-
cur1.Next = cur
-
cur = cur.Next
-
cur1 = cur1.Next
-
}else if cur.Val >=x{
-
cur2.Next = cur
-
cur = cur.Next
-
cur2 = cur2.Next
-
}
-
}
-
cur2.Next = nil
-
cur1.Next = dummnyhead2.Next
-
return dummnyhead1.Next
-
}
给定两个用链表表示的整数，每个节点包含一个数位。
这些数位是反向存放的，也就是个位排在链表首部。
编写函数对这两个整数求和，并用链表形式返回结果。
示例：
输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
输出：2 -> 1 -> 9，即912
进阶：假设这些数位是正向存放的，请再做一遍。
示例：
输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
输出：9 -> 1 -> 2，即912
模拟竖式计算即可。
-
/**
-
* Definition for singly-linked list.
-
* type ListNode struct {
-
* Val int
-
* Next *ListNode
-
* }
-
*/
-
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
-
up:=0;
-
ans:= &ListNode{-1,nil};
-
temp:=ans;
-
for l1!=nil || l2!=nil{
-
a,b:=0,0;
-
if(l1!=nil){
-
a=l1.Val;
-
}
-
if(l2!=nil){
-
b=l2.Val;
-
}
-
temp.Next=&ListNode{(a+b+up)%10,nil};
-
up=int((a+b+up)/10);
-
temp=temp.Next;
-
if(l1!=nil){
-
l1=l1.Next;
-
}
-
if(l2!=nil){
-
l2=l2.Next;
-
}
-
}
-
if(up!=0){
-
temp.Next=&ListNode{up,nil};
-
}
-
return ans.Next;
-
}
编写一个函数，检查输入的链表是否是回文的。
示例 1：
输入： 1->2
输出： false
示例 2：
输入： 1->2->2->1
输出： true
其实最优解应该原地反转一半，判断完再反转回去，我这个题是为了连一下go的列表。
-
/**
-
* Definition for singly-linked list.
-
* type ListNode struct {
-
* Val int
-
* Next *ListNode
-
* }
-
*/
-
func isPalindrome(head *ListNode) bool {
-
s:=make([]int,0)
-
for head!=nil{
-
s= append(s, head.Val)
-
head=head.Next
-
}
-
for i:=0;i< len(s)/2;i++{
-
if s[i]!=s[len(s)-1-i]{
-
return false
-
}
-
}
-
return true
-
}
给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同一节点（引用完全相同），则这两个链表相交。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
思路：调到长度一样以后，看能否走到一样的节点即可。
-
/**
-
* Definition for singly-linked list.
-
* type ListNode struct {
-
* Val int
-
* Next *ListNode
-
* }
-
*/
-
func getIntersectionNode(headA, headB *ListNode) *ListNode {
-
a,b:=0,0;
-
for temp:=headA;temp!=nil;temp=temp.Next{
-
a++;
-
}
-
for temp:=headB;temp!=nil;temp=temp.Next{
-
b++;
-
}
-
if(a>b){
-
for i:=a-b;i>0;i--{
-
headA=headA.Next;
-
}
-
}else if(a<b){
-
for i:=b-a;i>0;i--{
-
headB=headB.Next;
-
}
-
}
-
for headA!=nil && headB!=nil{
-
if(headA==headB){
-
return headA;
-
}
-
headA=headA.Next;
-
headB=headB.Next;
-
}
-
return nil;
-
}
文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。
原文链接：fantianzuo.blog.csdn.net/article/details/106203421
- 点赞
- 收藏
- 关注作者
评论（0）